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!