DEV Community

Cover image for DAY 10 - Subset Sums
Nayan Pahuja
Nayan Pahuja

Posted on • Edited on

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;
  }
Enter fullscreen mode Exit fullscreen mode

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).

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay