题解 | #牛群分组II#

知识点：

回溯/DFS

分析：

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

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

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

递归边界：

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

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

dfs(candidates,target,i + 1,CurSum); 不能重复选择，所以dfs中不再是i，而是i+1

完整代码 C++ ACcode

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param candidates int整型vector
     * @param target int整型
     * @return int整型vector<vector<>>
     */
    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 + 1, CurSum);
            path.pop_back();
            CurSum -= candidates[i];
        }
    }
    vector<vector<int> > cowCombinationSum2(vector<int>& candidates, int target) {
        dfs(candidates, target, 0, 0);
        return res;
    }
};