题解 | #牛群分组II#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param candidates int整型vector 
     * @param target int整型 
     * @return int整型vector<vector<>>
     */
    
    vector<vector<int> > ans; 

    void dfs(vector<int>& candidates, int target, int start, vector<int> v, int sum)
    {
        int len = candidates.size();
        if(sum==target)
        {
            ans.emplace_back(v);
            return;
        }

        if(start >= len)
            return;

        // 避免重复，也为了升序
        for(int i=start; i<len; ++i)
        {
            v.emplace_back(candidates[i]);
            dfs(candidates, target, i+1, v, sum + candidates[i]);
            v.pop_back();
        }

        return;
    }

    vector<vector<int> > cowCombinationSum2(vector<int>& candidates, int target) {
        // write code here

        sort(candidates.begin(),candidates.end());
        vector<int> v;
        dfs(candidates, target, 0, v, 0);

        return ans;
    }
};