题解 | #牛群喂食#

知识点：

回溯/DFS

分析：

1、遍历数组中的每一个数字。

2、递归枚举每一个数字可以选多少次，递归过程中维护一个target变量。如果当前数字小于等于target，我们就将其加入我们的路径数组path中，相应的target减去当前数字的值。也就是说，每选一个分支，就减去所选分支的值。

3、当target == 0时，表示该选择方案是合法的，记录该方案，将其加入res数组中。

递归边界：

1、 if(target < 0) ，表示当前方案不合法，返回上一层。

2、if(target == 0)，方案合法，记录该方案。

完整代码 C++ ACcode

    vector<vector<int> > res;
    vector<int> path;
    void dfs(vector<int>& candidates, int target,int u,int CurSum){
        if(CurSum > target) return;
        if(CurSum == target){res.push_back(path);return;}
        for(int i = u;i<candidates.size()&& CurSum + candidates[i] <= target;i++){
            path.push_back(candidates[i]);
            CurSum += candidates[i];
            dfs(candidates,target,i,CurSum);
            path.pop_back();
            CurSum -= candidates[i];
        }
    }
    vector<vector<int> > cowCombinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0,0);
        return res;
    }