※ 引述《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);
}
}
};