Given a array arr of integers, return the sums of all subsets in the list. Return the sums in any order.
Here’s the [Problem Link] to begin with.
Examples:
Input: arr[] = [2, 3] Output: [0, 2, 3, 5] Explanation: When no elements are taken then Sum = 0. When only 2 is taken then Sum = 2. When only 3 is taken then Sum = 3. When elements 2 and 3 are taken then Sum = 2+3 = 5.
Input: arr[] = [1, 2, 1] Output: [0, 1, 1, 2, 2, 3, 3, 4]
Explanation: The possible subset sums are 0 (no elements), 1 (either of the 1's), 2 (the element 2), and their combinations.
Input: arr[] = [5, 6, 7] Output: [0, 5, 6, 7, 11, 12, 13, 18] Explanation: The possible subset sums are 0 (no elements), 5, 6, 7, and their combinations.
Constraints:
1 ≤ arr.size() ≤ 15
0 ≤ arr[i] ≤ 104
Solution 1: Brute Force Approach (Maintaining Explicit Subset)
Intuition
Think of this like collecting items in a bag and calculating the total value each time! For every element in the array, we have two choices: either include it in our current subset or exclude it. We maintain an explicit list of the current subset and calculate its sum when we’ve made decisions for all elements. It’s like trying every possible combination of items and writing down the total value of each combination.
Detailed Approach
- Use Include/Exclude Pattern: For each element, try including it in the subset and excluding it.
- Maintain Explicit Subset: Keep track of the current subset as a list.
- Base Case: When we’ve processed all elements (index >= len(nums)), calculate sum of current subset and add to result.
- Backtracking: After exploring the “include” path, remove the element (pop) and explore the “exclude” path.
- Sort Result: Sort the final result as required by the problem.
Code
class Solution:
def solve(self, nums, index, subset, result):
# Base case: processed all elements
if index >= len(nums):
result.append(sum(subset)) # Calculate sum of current subset
return
# Choice 1: Include current element
subset.append(nums[index])
self.solve(nums, index + 1, subset, result)
# Backtrack: Remove current element
subset.pop()
# Choice 2: Exclude current element
self.solve(nums, index + 1, subset, result)
def subsetSums(self, arr):
result = []
self.solve(arr, 0, [], result)
result.sort() # Sort as required by problem
return resultCode Explanation
This solution uses the classic include/exclude backtracking pattern. We maintain an explicit subset list throughout the recursion. At each step, we first try including the current element (append to subset, recurse), then backtrack by removing it (pop), and try excluding it (recurse without the element). When we reach the base case (processed all elements), we calculate the sum of the current subset and add it to our results. The key insight is that we explore all 2^n possible subsets systematically.
Dry Run
graph TD
Root["solve(arr=[2,3], index=0, subset=[])<br/>Generate all subset sums"]
%% Level 0: index=0, element=2
Root --- A["Include 2<br/>subset=[2]<br/>index=1"]
Root --- B["Exclude 2<br/>subset=[]<br/>index=1"]
%% Level 1 from Include 2: index=1, element=3
A --- A1["Include 3<br/>subset=[2,3]<br/>index=2"]
A --- A2["Exclude 3<br/>subset=[2]<br/>index=2"]
%% Level 1 from Exclude 2: index=1, element=3
B --- B1["Include 3<br/>subset=[3]<br/>index=2"]
B --- B2["Exclude 3<br/>subset=[]<br/>index=2"]
%% Level 2: Base case - index >= len(nums)
A1 --- Result1["index=2 >= len(arr)<br/>✅ sum([2,3]) = 5<br/>Add 5 to result"]
A2 --- Result2["index=2 >= len(arr)<br/>✅ sum([2]) = 2<br/>Add 2 to result"]
B1 --- Result3["index=2 >= len(arr)<br/>✅ sum([3]) = 3<br/>Add 3 to result"]
B2 --- Result4["index=2 >= len(arr)<br/>✅ sum([]) = 0<br/>Add 0 to result"]
%% Final result
Result1 --- Final["Final Result: [5, 2, 3, 0]"]
Result2 --- Final
Result3 --- Final
Result4 --- Final
%% Styling
style Result1 fill:#90EE90
style Result2 fill:#90EE90
style Result3 fill:#90EE90
style Result4 fill:#90EE90
style Final fill:#90EE90
style Root fill:#E6E6FA
Click here for better visualization.
Time and Space Complexity
- Time Complexity: O(2^n × n) – We explore 2^n subsets, and for each subset we calculate sum() which takes O(n) time
- Space Complexity: O(n) – Maximum depth of recursion stack plus space for the subset list
Simplifying It
This approach is like having a shopping cart and for every item you see, you try putting it in the cart, check the total, then try not putting it in the cart and check that total too. You write down every possible total you can make.
Solution 2: Optimal Approach (Running Sum)
Intuition
Instead of maintaining the entire subset and calculating its sum every time, why not just keep track of the running total? It’s like having a running tally on a calculator – as you decide to include or exclude each number, you just add to or keep the current total the same. This eliminates the need to recalculate the sum from scratch each time, making each recursive call O(1) instead of O(n).
Detailed Approach
- Pass Running Total: Instead of maintaining subset list, pass the current sum as a parameter.
- Include Choice: Add current element to the running total and recurse.
- Exclude Choice: Keep the running total same and recurse.
- Base Case: When all elements processed, add the current total to results.
- No Backtracking Needed: Since we’re not modifying any shared state, no explicit backtracking required.
Code
class Solution:
def solve(self, nums, total, index, result):
# Base case: processed all elements
if index >= len(nums):
result.append(total) # Add current running total
return
# Choice 1: Include current element (add to running total)
Sum = total + nums[index]
self.solve(nums, Sum, index + 1, result)
# Choice 2: Exclude current element (keep same total)
Sum = total # This line is actually redundant
self.solve(nums, Sum, index + 1, result)
def subsetSums(self, arr):
result = []
self.solve(arr, 0, 0, result) # Start with total=0, index=0
result.sort()
return resultCode Explanation
This optimal solution eliminates the need for maintaining an explicit subset list and calculating sums repeatedly. We pass the running total as a parameter – when we include an element, we pass total + nums[index], when we exclude it, we pass just total. Since we’re not modifying any shared data structure, we don’t need explicit backtracking. Each recursive call does O(1) work, making this much more efficient than the brute force approach.
Dry Run
graph TD
Root["solve(arr=[2,3], total=0, index=0)<br/>Generate all subset sums with running total"]
%% Level 0: index=0, element=2
Root --- A["Include 2<br/>total = 0 + 2 = 2<br/>index=1"]
Root --- B["Exclude 2<br/>total = 0<br/>index=1"]
%% Level 1 from Include 2: index=1, element=3
A --- A1["Include 3<br/>total = 2 + 3 = 5<br/>index=2"]
A --- A2["Exclude 3<br/>total = 2<br/>index=2"]
%% Level 1 from Exclude 2: index=1, element=3
B --- B1["Include 3<br/>total = 0 + 3 = 3<br/>index=2"]
B --- B2["Exclude 3<br/>total = 0<br/>index=2"]
%% Level 2: Base case - index >= len(nums)
A1 --- Result1["index=2 >= len(arr)<br/>✅ Add total=5 to result"]
A2 --- Result2["index=2 >= len(arr)<br/>✅ Add total=2 to result"]
B1 --- Result3["index=2 >= len(arr)<br/>✅ Add total=3 to result"]
B2 --- Result4["index=2 >= len(arr)<br/>✅ Add total=0 to result"]
%% Final result
Result1 --- Final["Final Result: [5, 2, 3, 0]"]
Result2 --- Final
Result3 --- Final
Result4 --- Final
%% Styling
style Result1 fill:#90EE90
style Result2 fill:#90EE90
style Result3 fill:#90EE90
style Result4 fill:#90EE90
style Final fill:#90EE90
style Root fill:#E6E6FAClick here for better visualization.
Time and Space Complexity
- Time Complexity: O(2^n) – We still explore 2^n subsets, but each call is now O(1)
- Space Complexity: O(n) – Only recursion stack space needed, no extra data structures
Simplifying It
This approach is like having a mental running total – as you decide whether to “buy” each item, you either add its price to your mental total or keep it the same. You write down your final total at the end of each shopping trip, without needing to look back at what you actually bought.
Summary
| Approach | Time | Space | Difficulty | Best For |
|---|---|---|---|---|
| Brute Force (Explicit Subset) | O(2^n × n) | O(n) | Easy | Understanding the concept |
| Optimal (Running Sum) | O(2^n) | O(n) | Medium | Production code |
The optimal approach is clearly superior as it eliminates the redundant sum calculation at each leaf node, reducing the time complexity by a factor of n. The brute force approach is more intuitive for beginners to understand the subset generation process.
The key insight for Subset Sums is realizing that we don’t need to store the actual subsets, just their sums. By maintaining a running total instead of an explicit subset, we can make each recursive call O(1), which is a common optimization technique in backtracking problems!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
