Re: [閒聊] 每日leetcode

[sixB (6B)]

※ 引述《dont (dont)》之銘言：
: 40. Combination Sum II

找組合

要去掉重複的

原本想說懶得sort

套了一層multiset 外面再套一層set

MLE

跑去看constraint 這麼小

乖乖擺格子

現在看一看 好像也可以dpㄟ==

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        //1 <= target <= 30
        //1 <= candidates[i] <= 50
        //1 <= candidates.length <= 100
        vector<int> can(31, 0);
        for(int i: candidates){
            if(i > 30) continue;
            can[i]++;
        }
        vector<vector<int>> res;
        comb(res, can, {}, target, target);
        return res;
    }
    void comb(vector<vector<int>>& res, vector<int>& can, vector<int> cur,  int idx, int target){
        if(target == 0){
            res.push_back(cur);
            return;
        }
        if(target < 0) return;
        if(idx < 0) return;
        for(int i = 0; i <= can[idx]; i++){
            comb(res, can, cur, idx-1, target);
            target -= idx;
            if(target < 0) return;
            cur.push_back(idx);
        }

    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723557731.A.4B0.html
推 orangeNoob: 大師