## 40. Combination Sum II

Description:

https://leetcode.com/problems/combination-sum-ii/#/description

Actually this problem is quite similar to that of “Combination Sum”. The difference is that we cannot reuse elements and the result must be unique.

Generally,

The keypoint is to use the void() as the helper function and use result & intermediate as the parameters.
Another keypoint is to use the “start” to record the process.
Another point is to use the pop_back() function. I only remembered clear(), but there is no proper way to use clear.

class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int> intermediate;
vector<vector<int>> result;
helper(candidates, target, 0, intermediate, result);
return result;
}
void helper(vector<int> candidates, int gap, int start, vector<int>& intermediate, vector<vector<int>>& result)
{
if (gap == 0)
{
result.push_back(intermediate);
return;
}
int i = start;
while(i < candidates.size())
{
if (gap < candidates[i])
return;
intermediate.push_back(candidates[i]);
helper(candidates, gap – candidates[i], i + 1, intermediate, result);
intermediate.pop_back();
while ((i < candidates.size() + 1) && candidates[i] == candidates[i + 1]) i++; // Use this, so we will not recalculate duplicate elements
i ++;
}
}
};

Time:

Beats 50.44% in c++. My algorithm is quite similar to the algorithm posted by others, which means that I’m learning something!

## 15. Three Sum

The description of the problem is : https://leetcode.com/problems/3sum/#/description

Generally, The time complexity is O(n^2). Use for loop and squeeze rule to solve this problem.

For boundary condition: consider when the number in candidates is less than 3, then there is no solution.

The solution:

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
if (nums.size() < 3) return{};
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() – 2; i++)
{
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i – 1])
continue;
int left = i + 1;
int right = nums.size() – 1;

while (left < right)
{
if (nums[right] < 0)
break;
int tmp = nums[i] + nums[left] + nums[right];
if (tmp == 0)
{
result.push_back({ nums[i], nums[left], nums[right] });
while (left < right && nums[left] == nums[left + 1])
left++;
while (left < right && nums[right] == nums[right – 1])
right–;
++left;
–right;
}
else if (tmp < 0)
left++;
else
right–;
}
}
return result;
}
};

Tips:

How to remove the duplicate elements in vector?

result.erase(std::unique(result.begin(), result.end()), result.end());