Day 9 Recursion | Striver 180 | takeUforward
Post
Cancel

# Day 9 Recursion | Striver 180 | takeUforward

## Problem 1: Subset Sums

Given a list arr of N integers, print sums of all subsets in it.

Note: Return all the element is increasing order.

### Brute

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: vector<int> subsetSums(vector<int> arr, int N) { vector<int> ans; long long total = 1 << n; for (long long i = 0; i < total; i++) { long long sum = 0; for (int j = 0; j < n; j++) if (i & (1 << j)) sum += arr[j]; ans.push_back(sum); sort(ans.begin(), ans.end()); return ans; } }; 

### Optimal

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: void solve(int index, int sum, int N, vector<int> &arr, vector<int> &ans) { if(index == N){ ans.push_back(sum); return; } solve(index+1, sum + arr[index], N, arr, ans); solve(index+1, sum, N, arr, ans); } vector<int> subsetSums(vector<int> arr, int N) { vector<int> ans; solve(0, 0, N, arr, ans); sort(ans.begin(), ans.end()); return ans; } };