combination sum@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 set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

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 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] 

» Solve this problem

思路还是dynamic programming,用recursion做。和前面已经做过的一道题思路很像，只需要改一些细节，要注意这个元素本身可以重复使用，所以不需要设VISITED[]，但是很可能会出现重复的COMBINATION，所以要先SORT ARRAY。

	class Solution {
	public:
	void combineSum(vector<int> &candidates, int &sum, int begin, int target, 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)
	{
	solution.push_back(candidates[i]);
	sum+=candidates[i];
	combineSum(candidates, sum, i, target, solution, res);
	sum-=candidates[i];
	solution.pop_back();
	}
	}
	}
	vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<int> solution;
	vector<vector<int> > res;
	if(candidates.empty()) return res;
	sort(candidates.begin(), candidates.end());
	int sum=0;
	combineSum(candidates, sum, 0, target, solution, res);
	return res;
	}
	};

view raw combination sum I hosted with ❤ by GitHub