DAY 10 - Subset Sums

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-10.The goal is simple. I will solve one or more than one leetcode/gfg problem a day and post what I learnt. I am confident that this will help me improve my concepts and help me be more consistent in my practice. Looking forward to a positive interaction with all of you.

Day 10 Problem 1: Subset Sums

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

Example:

Input:
N = 2
arr[] = {2, 3}
Output:
0 2 3 5
Explanation:
When no elements is taken then Sum = 0.
When only 2 is taken then Sum = 2.
When only 3 is taken then Sum = 3.
When element 2 and 3 are taken then
Sum = 2+3 = 5.

Intuition:

The main idea is that you select one index. Then you get on further and choose the next index from array and choose if you want to add the sum or not. Iterating through all these options and adding their sums will give us the answer.

It is clear that we can minimize our code density if we use a recursive approach to solve this. Either we pick the index or we do not.

Approach:

• If all options are navigated through, return the answer.
• Use recursive call to either add the index to sum or leave the index.
• Increment the index by 1.
• Store the sum in the result array.

Code:

void subsetSum(int ind, vector < int > & arr, int n, vector < int > & ans, int sum) {
      if (ind == n) {
        ans.push_back(sum);
        return;
      }
      //element is picked
      subsetSum(ind + 1, arr, n, ans, sum + arr[ind]);
      //element is not picked
      subsetSum(ind + 1, arr, n, ans, sum);
    }
  vector < int > subsetSums(vector < int > arr, int n) {
    vector < int > ans;
    subsetSum(0, arr, n, ans, 0);
    return ans;
  }

Complexity Analysis:

Time Complexity:O(2^N)
Space Complexity:O(2^N)
Explanation: Here since we use recursive stack as well to store the result to find the answer. Space complexity will be O(2^N).