using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; #define REP(x, l, u) for(ll x = l;x<u;x++) #define RREP(x, l, u) for(ll x = l;x>=u;x--) #define se second #define fi first #define input(s) getline(cin,s) typedef vector<int> VI; typedef unordered_map<int,int> UMAPI; const ll mod = 1e9 + 7; #define len(x) x.size() class Solution { vector<VI> ans; VI tmp; void search(VI& candidates, int rem, int ind){ if(rem == 0){ ans.emplace_back(tmp); return; } REP(i, ind, len(candidates)){ if(i != ind && candidates[i] == candidates[i-1]) continue; if(candidates[i] <= rem){ tmp.emplace_back(candidates[i]); search(candidates, rem - candidates[i], i + 1); tmp.pop_back(); } else break; } } public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); search(candidates, target, 0); return ans; } };
思路上基本和 39 一样,排序然后搜索。只需要注意同一种元素打头的搜索只需要一次就行了。比如[2, 2, 3],当遍历并深搜这个数组的时候,遍历到第二个 2 的时候跳过就行了。