leetcode Combination Sum 使用会合中的元素求和得到目标值

leetcode Combination Sum 使用集合中的元素求和得到目标值

http://oj.leetcode.com/problems/combination-sum/

题目：

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

  枚举所有可能，使用集合中的元素求和，得到目标值。数组path记录满足条件的解。

  数组res记录所有的解。

  函数com从集合中遍历集合candidate并回溯 并把满足条件的解放入res.

  完整代码如下：

  #include <iostream>#include <vector>#include <algorithm>using namespace std;class Solution {public:// start 从candidates开始的位置, sum当前的和,target目标和,path存放满足条件的值,res 存放所有结果void com(vector<int> &candidates, int start, int sum, int target, vector<int> &path, vector<vector<int> > &res){if(sum>target)//超出目标值 退出return ;if(sum == target)// 找到一种解{res.push_back(path);return ;}int len = candidates.size();for(int i=start; i<len; i++){path.push_back(candidates[i]);//存放当前值com(candidates, i, sum+candidates[i], target, path, res);path.pop_back();//回溯}}vector<vector<int> > combinationSum(vector<int> &candidates, int target){sort(candidates.begin(), candidates.end());vector<vector<int> > res;vector<int> path;com(candidates, 0,0, target, path, res);return res;}};int main(){vector<vector<int> > re;vector<int> c;int n,t;int i,j;cin>>t;while(cin>>n){c.push_back(n);}Solution s;re = s.combinationSum(c, t);for(i=0; i<re.size(); i++){for(j=0; j<re[i].size(); j++)cout<<re[i][j]<<" ";cout<<endl;}return 0;}