這題四年前有寫過,最近在做複習
我用的方式應該算是很general的方式來解
backtracking or DFS(?) 不過缺點會用掉一個nlogn的sorting
然後從小的開始選擇要不要pick到vector cur中,然後依序遞迴下去
一開始只有單純遞迴,發現會算到重覆的case
只好改用loop避開
push就是選了這個subset,因為可以重複使用,這裡index不++,進入遞迴
pop的狀況就是不選or不再選這個subset
看討論區基本上要不要pick的題目(subset 排列組合之類的)好像都可以這樣的方式解
class Solution { public: vector<vector<int>> res; vector<int> candidates; vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); this->candidates = candidates; vector<int> dummy; helper(0, target, dummy); return res; } void helper (int i, int target, vector<int>& cur) { if (target == 0) { res.emplace_back(cur); return; } for (; i < candidates.size(); i++) { if(candidates[i] > target) break; cur.emplace_back(candidates[i]); helper(i, target-candidates[i], cur); cur.pop_back(); } } };