Untitled
unknown
c_cpp
2 years ago
983 B
10
Indexable
// Recursive - Entry function vector<int> subsetSums(vector<int> arr, int N) { vector<int> res; subsetSumsUtil(arr, N, res, 0, 0); return res; } void subsetSumsUtil(vector<int> &arr, int N, vector<int> &res, int i, int sum) { if (i == N) { res.push_back(sum); return; } // Not pick the element at index i subsetSumsUtil(arr, N, res, i+1, sum); // Pick the element at index i subsetSumsUtil(arr, N, res, i+1, sum + arr[i]); } // Iterative vector<int> subsetSums(vector<int> arr, int N) { vector<int> res; res.push_back(0); // Sum of all possible combinations from A[0 .... i] = // sum of all possible combinations from A[0 ... i-1] // & (A[i] + sum of all possible combinations from A[0 ... i-1]) for (int i = 0; i < N; i++) { int resSz = res.size(); for (int j = 0; j < resSz; j++) res.push_back(res[j] + arr[i]); } return res; }
Editor is loading...