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;
}
|
