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

題目：

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 (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 

2,3,6,7

 and target 

7

, 

A solution set is: 

[7]

[2, 2, 3]

枚舉所有可能，使用集合中的元素求和，得到目标值。

數組v維護一種可能情況下，每種元素使用的個數。

用dfs周遊所有可能的情況。

int len;
vector<int> v;
vector<vector<int> > l;
class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        len=candidates.size();
        sort(candidates.begin(),candidates.end());
        v.clear();
        l.clear();        
        if(len==0)return l;
        v.resize(len);
        hehe(0,target,candidates);
        return l;        
        
    }
    
    void hehe(int p,int target,vector<int > &candidates)
    {
      
        if(p==len)
        {
            if(target!=0)return;
            vector<int> temp;
            for(int i=0;i<len;++i)
            {                        
                for(int j=0;j<v[i];++j)
                    temp.push_back(candidates[i]);                
            }
            l.push_back(temp);
            return;            
        }
        for(int i=0;i<=target;i+=candidates[p])
        {
            
            v[p]=i/candidates[p];
            hehe(p+1,target-i,candidates);
        }
        return;
    }
    
    
};