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.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

思路：回溯法+深度优先

当然首先就是对数组排序，调用sort函数即可。关键在于回溯法；

编写的一个sumHelper函数，前面两个分别为候选数字，目标数字，后面是在目标数组中的索引值，和目标数组长度.

一开始，不会，因为是求和，而不是判断，后来查看程序，发现使用一个target是否为0的判断即可，化和为差，如果求出来和是目标数字，那么刚刚的和与目标数字的差即为0，非常棒的想法。

对于这类题目，思路只能讲到这里，还是把实例中的各种顺序罗列出来，应该能够方便大家理解的。

2,3,6,7 并且目标数字为 7,

2，2，2，2 --- 2，2，3 --- 2 , 2 ，6 --- 2 ， 3 ，3  --- 2，6 , 6  

...........

大体过程如此所所示。

代码：

class Solution {
public:
//
        vector<int>temp;
        vector<vector<int> >result;
        
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        
        sumHelper(candidates,target,0,candidates.size());
        return result;
    }
    
    void sumHelper(vector<int>& candidates,int target,int index,int length){
        //index代表数组索引值，length代表数组长度
        if(target==0){
            //这里很巧的是，别人用sum求和，他不用，他是相减，只要等于0了，就会存入数组中。
            result.push_back(temp);
            return;//不需要返回
        }
        if(index>=length||target<0){//因为是求减法，如果不相等，立即返回||
                                   //还有一种是索引值大于数组长度
            return;
        }
        
        for(int i=index;i<=length-1;i++){
            temp.push_back(candidates[i]);
            sumHelper(candidates,target-candidates[i],i,length);
            temp.pop_back();
        }
    }
};