LeetCode Q40: Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6] 

Solution:
The difficulty of this problem is how to avoid duplicate results. If using recursion, to avoid duplicate results, we have to make sure such results are included in previous search. So, in recursion, the first part has to search all possible cases. Then, we can skip duplicate elements after that. Here, I wrote two codes which are basically the same.
Code 1:

	class Solution {
	public:
	void helper(vector<int> candidates, int target, vector<vector<int> >& res, vector<int>& cur, int idx, int sum){
	if(sum==target){
	res.push_back(cur);
	return;
	}
	if(sum>target||idx>=candidates.size())
	return;
	for(int i=idx; i<candidates.size(); i++){
	cur.push_back(candidates[i]);
	helper(candidates, target, res, cur, i+1, sum+candidates[i]);
	cur.pop_back();
	while(candidates[i]==candidates[i+1]) i++;
	}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
	vector<vector<int> > res;
	vector<int> cur;
	if(candidates.empty())
	return res;
	sort(candidates.begin(), candidates.end());
	helper(candidates, target, res, cur, 0, 0);
	return res;
	}
	};

view raw Q40-1.cpp hosted with ❤ by GitHub

Code 2:

	class Solution {
	public:
	void helper(vector<int> candidates, int target, vector<vector<int> >& res, vector<int>& cur, int idx, int sum){
	if(sum==target){
	res.push_back(cur);
	return;
	}
	if(sum>target||idx>=candidates.size())
	return;
	cur.push_back(candidates[idx]);
	helper(candidates, target, res, cur, idx+1, sum+candidates[idx]);
	cur.pop_back();
	while(candidates[idx]==candidates[idx+1]) idx++;
	helper(candidates, target, res, cur, idx+1, sum);
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
	vector<vector<int> > res;
	vector<int> cur;
	if(candidates.empty())
	return res;
	sort(candidates.begin(), candidates.end());
	helper(candidates, target, res, cur, 0, 0);
	return res;
	}
	};

view raw Q40-2 hosted with ❤ by GitHub