combination sum II@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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 (a₁, a₂, � , a_k) must be in non-descending order. (ie, a₁ ? a₂ ? � ? a_k).
• 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] 

» Solve this problem

思路没太多差别，关键还是去重复，用的方法也和PERMUTATIONS II一样。

	class Solution {
	public:
	void combineSum(vector<int> &candidates, int &sum, int begin, int target, vector<int> &visited, vector<int> &solution, vector<vector<int> > &res)
	{
	if(sum==target)
	{
	res.push_back(solution);
	return;
	}
	if(sum>target)
	return;
	for(int i=begin; i<candidates.size(); i++)
	{
	if(candidates[i]<=target&&visited[i]==0)
	{
	if(i>0 && candidates[i]==candidates[i-1] && visited[i-1]==0)
	continue;
	visited[i]=1;
	solution.push_back(candidates[i]);
	sum+=candidates[i];
	combineSum(candidates, sum, i, target, visited, solution, res);
	sum-=candidates[i];
	solution.pop_back();
	visited[i]=0;
	}
	}
	}
	vector<vector<int> > combinationSum2(vector<int> &num, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<int> solution;
	vector<vector<int> > res;
	vector<int> visited(num.size(), 0);
	if(num.empty()) return res;
	sort(num.begin(), num.end());
	int sum=0;
	combineSum(num, sum, 0, target, visited, solution, res);
	return res;
	}
	};

view raw combination sum II hosted with ❤ by GitHub