Subset Sum

Easy
0/40
profile
Contributed by
140 upvotes
Asked in companies
SAP LabsOlaAmazon

Problem statement

You are given an array 'nums' of ‘n’ integers.


Return all subset sums of 'nums' in a non-decreasing order.


Note: 
Here subset sum means sum of all elements of a subset of 'nums'. A subset of 'nums' is an array formed by removing some (possibly zero or all) elements of 'nums'.


For example 
Input: 'nums' = [1,2]

Output: 0 1 2 3

Explanation:
Following are the subset sums:
0 (by considering empty subset)
1 
2
1+2 = 3
So, subset sum are [0,1,2,3].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer ‘n’, denoting the size of the array 'nums'.

The second line of input contains ‘n’ space-separated integers denoting elements of the array 'nums'.
Output Format : 
Return the sum of all the subsets of 'nums' in non-decreasing order.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
3
1 2 3
Sample output 1 :
0 1 2 3 3 4 5 6
Explanation For Sample Output 1:
For the first test case,
Following are the subset sums:
0 (by considering empty subset)
1
2
1+2 = 3
3
1+3 = 4
2+3 = 5
1+2+3 = 6
So, subset-sums are [0,1,2,3,3,4,5,6]
Sample Input 2 :
2 
4 5
Sample output 2 :
0 4 5 9
Expected Time Complexity:
Try to do this in O(n*2^n).
Constraints:
1 <= n <= 15
0 <= nums[i] <= 5000

Time limit: 1 sec
Hint

Calculate the sum for every possible subset.

Approaches (2)
Recursion

The basic idea is to go over recursively to find every possible subset. For every element, we have two choices

1. Include the element in our subset.

2. Don’t include the element in our subset.

When we include an element in the set then it will contribute to the subset sum.

 

Let us define a function “subset( i, sum, num, ans)”, where ‘i’ is the current index of the array we are at, “sum” is the current sum of the current subset, “num” is the given vector, “ans” is the vector which stores the sum of all possible subsets. 

 

Here is the algorithm:

  • subset function:
    • If i is equal to the size of the “num” vector
      • Insert the “sum” in the “ans” vector.
      • Return.
    • subset(i+1, sum+num[i], num, ans)
    • subset(i+1, sum, num, ans)
  • given function:
    • Declare a vector “ans” which stores all possible subset sums. It will pass by reference in the “subset” function.
    • subset(0, 0, num, ans).
    • Sort the “ans” vector.
    • Return “ans”.
Time Complexity

O(n * 2^n ), where ‘n’ is the size of the array.

 

Each element of the array has 2 choices whether to include in a subset or not. So there is a 2^n number of subsets. Sorting the ‘ans’ takes O((2^n)*log(2^n)) time, which can be simplified as O(n*(2^n)). 

Hence, the overall time complexity will be O( n*(2^n) ).

Space Complexity

O( n ), where ‘n’ is the size of the array.
 

Since we are using a recursive function, the space complexity will be equal to the stack size of that function which is O(n). Hence the overall space complexity will be O(n).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Subset Sum
Full screen
Console