LeetCode

LeetCode-40 组合总和 II

nkul · 10月3日 · 2020年 · 24次已读

LeetCode-39 组合总和

2020-10-3 0

和上题类似,但是本题限制了每个数只能使用一次,所以dfs函数内部需要计算出每个数的个数cnt,添加一个条件即可!

class Solution {
public:
    vector> ans;
    vector path;
    vector> combinationSum2(vector& c, int target) {
        sort(c.begin(),c.end());
        dfs(c,0,target);
        return ans;
    }

    void dfs(vector& c,int u, int target){
        if(target == 0){
            ans.push_back(path);
            return;
        }
        if(u == c.size()) return;
        /**
        以下内容相比上题添加了个数限制!
        */
        int k = u + 1;
        while(k < c.size() && c[k] == c[u]) k ++;
        int cnt = k - u;
        for(int i = 0 ;i * c[u] <= target && i <= cnt;i++){
            dfs(c, k, target - c[u] * i);
            path.push_back(c[u]);
        }

        for(int i = 0 ;i * c[u] <= target && i <= cnt ;i++){
            path.pop_back();
        }
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!