[LeetCode]Combination Sum II

和I类似的题目，但是每个数只能选一次。类似I的做法，注意去重即可。去重和Permutation II稍有不同，比如1，7和7，1是不同的permutation但是在这一题当中算是一样的。所以我们需要先sort，然后保证每次跳过重复选过的即可。时间复杂度O(k)，k为结果集的大小，空间复杂度O(len)，len为array的长度。代码如下：

	class Solution {
	public:
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
	vector<vector<int>> res;
	vector<int> curr;
	sort(candidates.begin(),candidates.end());
	backtrack(res, curr, candidates, target, 0, 0);
	return res;
	}
	private:
	void backtrack(vector<vector<int>>& res, vector<int>& curr, vector<int>& candidates, int target, int currSum, int i)
	{
	if(currSum > target)
	return;
	if(currSum == target)
	{
	res.push_back(curr);
	return;
	}
	for(int j = i; j < candidates.size(); ++j)
	{
	if(j > i && candidates[j] == candidates[j - 1])
	continue;
	int num = candidates[j];
	curr.push_back(num);
	backtrack(res, curr, candidates, target, currSum + num, j + 1);
	curr.pop_back();
	}
	}
	};

view raw Combination Sum II.cpp hosted with ❤ by GitHub