|
This post is completed by 1 user
|
Add to List |
440. Given an array, Print sum of all subsets
Objective: Given an array of numbers, write an algorithm to print all the subsets sum individually.
Example:
Given Input: [1, 2] Output: 3 1 2 0 Explanation: subsets are [0], [1], [2], [1, 2] Given Input: [2, 4, 6] 12 6 8 2 10 4 6 0
Approach: Recursion
Every element of the array has two choices, whether to include that element in the subset or exclude that element from the subset. So initialize sum = 0, now for each element in the array - add it to sum and make a recursive call, do not add it to sum and make a recursive call. Print the sum at the base case when the current element is the last element of an array.
Time Complexity: O(2^N)
Output:
Given Input: [2, 4, 6] 12 6 8 2 10 4 6 0