题解 | #牛群喂食# 回溯

知识点

回溯

思路

获取所有的方法，可以使用回溯的方法。首先先把备选的数字进行从小排序，之后讨论每个位置选几个的方法来进行递归，直到到达备选数组的末尾或者总和大于要求时递归终止。当满足总和正好等于要求时加入答案数组。

由于我们是一个一个加入路径，而且回溯的备选数组是从小到大的，因此我们获得的路径是符合字典序的；要求字典序降序，所以我们把答案反转即可。

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param candidates int整型vector 
     * @param target int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > cowCombinationSum(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 sum, int u) {
            if (u == candidates.size() or sum <= 0) {
                if (sum == 0) res.push_back(path);
                return;
            }
            for (int i = 0; i * candidates[u] <= sum; i ++) {
                dfs(path, sum - i * candidates[u], u + 1);
                path.push_back(candidates[u]);
            }
            while (path.size() and path.back() == candidates[u]) path.pop_back();
        };
        vector<int> p;
        dfs(p, target, 0);
        reverse(res.begin(), res.end());
        return res;
    }
};