leetcode39. 组合总和

思路如下：

1、遍历数组中的每一个数字。
2、递归枚举每一个数字可以选多少次，递归过程中维护一个target变量。如果当前数字小于等于target，我们就将其加入我们的路径数组path中，相应的target减去当前数字的值。也就是说，每选一个分支，就减去所选分支的值。
3、当target == 0时，表示该选择方案是合法的，记录该方案，将其加入res数组中。

作者：lin-shen-shi-jian-lu-k
链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-zui-tong-su-yi-dong-de-da-6qyl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:

    vector<vector<int>>res; //记录答案
    vector<int>path;   //记录路径

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,0,target);
        return res;
    }

    void dfs(vector<int>&c,int u ,int target)
    {
        if(target < 0) return ;   //递归边界
        if(target == 0)
        {
            res.push_back(path);  //记录答案
            return ;
        }
        for(int i = u; i < c.size(); i++){
            if( c[i] <= target)  
            {
                path.push_back(c[i]);   //加入路径数组中
                dfs(c,i,target -  c[i]);// 因为可以重复使用，所以还是i
                path.pop_back();        //回溯，恢复现场
            }
        }
    }
};