Re: [閒聊] 每日leetcode
※ 引述《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
推
08/13 22:02,
1年前
, 1F
08/13 22:02, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 705 之 1548 篇)：