1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| void helper(vector<vector<int>>& res, vector<pair<int,int>>& A, int rem, int p, vector<int>& now) { if(rem == 0) res.push_back(now); else if(p == A.size() or A[p].first > rem) return; else { auto [v, cnt] = A[p]; for(int i = min(cnt, rem / v); i >= 0; i--) { for(int j = 0; j < i; j++) now.push_back(v); helper(res,A,rem - i * v, p + 1, now); for(int j = 0; j < i; j++) now.pop_back(); } } } vector<vector<int>> Solution::combinationSum(vector<int> &A, int B) { map<int, int> mp; for(auto& a : A) mp[a]++; vector<pair<int,int>> freq; for(auto [k,v] : mp) freq.push_back({k,v}); vector<vector<int>> res; helper(res, freq, B, 0, vector<int>() = {}); return res; }
|