题解 | #牛群分组II# 回溯

知识点

回溯

思路

每个数字只能选一次，要获取全部的方案，可以采用回溯的方法。从左到右选择是否把当前元素加入路径，当到达末尾或者累积总和大于等于要求时停止。

当总和等于要求值时加入答案。由于我们优先选取当前元素的路径，所以得到字典序递增的答案。

AC code(C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param candidates int整型vector 
     * @param target int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > cowCombinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        function<void(vector<int>&, int, int)> dfs = [&](vector<int>& path, int u, int sum) {
            if (u == candidates.size() or sum >= target) {
                if (sum == target) {
                    res.push_back(path);
                }
                return;
            }
            path.push_back(candidates[u]);
            dfs(path, u + 1, sum + candidates[u]);
            path.pop_back();
            dfs(path, u + 1, sum);
        };
        vector<int> p;
        dfs(p, 0, 0);
        return res;
    }
};