Problem Statement

Given an array nums of n integers. Return sum of all subsets of the array nums.

Output can be printed in any order.

Examples

Example 1:

Input: nums = [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 is taken, then  Sum = 5

Example 2:

Input: nums = [5, 2, 1]
Output: [0, 1, 2, 3, 5, 6, 7]

Explanation:
When no element is taken then Sum = 0
When only 5 is taken then Sum = 5
When only 2 is taken then Sum = 2
When only 1 is taken then Sum = 1
When element 5 and 2 is taken then Sum = 5 + 2 = 7
When element 5 and 1 is taken then Sum = 5 + 1 = 6
When element 2 and 1 is taken then Sum = 2 + 1 = 3
When element 5, 2 and 1 is taken then Sum = 5 + 2 + 1 =  8

Example 3:

Input: nums = [1]
Output: [0, 1]

Explanation:
When no element is taken then Sum = 0
When element 1 is taken then Sum = 1

Different Approaches

1️⃣ Recursion

Real-life Analogy

Consider a scenario where an individual is tasked with determining all possible expenditure amounts from a set of available items, each with a specific price. The process begins with an empty expenditure and involves evaluating each item sequentially. For each item, a decision is made whether to include its price in the current expenditure or not. This decision-making process continues until all items have been considered, resulting in a comprehensive list of all possible total expenditures.

Recursive Intuition

In the recursive approach, the problem is decomposed into simpler sub-problems by making binary decisions for each item: either include the item in the current sum or exclude it. The recursion explores both possibilities for every item until all items are processed. The base case is reached when all items have been evaluated, at which point the accumulated sum is recorded. This method ensures that every potential combination of included and excluded items is considered, thereby generating all possible subset sums.

Approach:

1. Initialize an empty list to store the results of subset sums.
2. Define a recursive function that takes the current index, current sum, the input array, and the result list as parameters.
3. In the recursive function, check if the current index has reached the end of the array. If so, add the current sum to the result list and return.
4. Recursively call the function twice:
   1. First call includes the current element in the sum, incrementing the index.
   2. Second call excludes the current element from the sum, incrementing the index.
5. Start the recursion with the initial index 0 and sum 0.
6. Return the result list containing all possible subset sums after the recursion completes.

Dry Run:

At each level, we decide whether to include or exclude the current element. The recursion tree for nums = [2, 3] is as follows:

                     solve(index=0, output=[])
                          |
           ┌──────────────┴──────────────┐
           |                             |
 Include 2 (sum: 2)               Exclude 2 (sum: 0)
           |                             |
    solve(index=1, output=[2])      solve(index=1, output=[])
           |                             |
     ┌─────┴─────┐                 ┌─────┴─────┐
     |           |                 |           |
Include 3    Exclude 3         Include 3    Exclude 3
(sum: 5)    (sum: 2)           (sum: 3)    (sum: 0)
     |           |                 |           |
solve(index=2)   solve(index=2)    solve(index=2)   solve(index=2)

Detailed Steps

1. solve(index=0, output=[]):
   • Start with an empty subset (output=[]).
   • Option 1: Include 2 → output = [2], recurse with index=1.
   • Option 2: Exclude 2 → output = [], recurse with index=1.
2. solve(index=1, output=[2]):
   • Subset contains [2].
   • Option 1: Include 3 → output = [2, 3], recurse with index=2.
   • Option 2: Exclude 3 → output = [2], recurse with index=2.
3. solve(index=1, output=[]):
   • Subset is still empty (output=[]).
   • Option 1: Include 3 → output = [3], recurse with index=2.
   • Option 2: Exclude 3 → output = [], recurse with index=2.
4. Base Cases (index=2):
   • For each leaf node where index=2, we calculate the sum of output:
     • [2, 3] → sum = 5
     • [2] → sum = 2
     • [3] → sum = 3
     • [] → sum = 0

Final Output

The result vector after traversing the entire tree will be:

result = [5, 2, 3, 0];

Each path in the tree represents a subset:

• [2, 3] has sum 5.
• [2] has sum 2.
• [3] has sum 3.
• [] (empty subset) has sum 0.

Code:

#include <bits/stdc++.h>
using namespace std;


class Solution {
private: 
    // Helper function to calculate subset sums
    void func(int ind, int sum, vector<int> &nums, vector<int> &ans) {
        // Base case: if index reaches the end of the nums vector
        if(ind == nums.size()) {
            // Add the current sum to the ans vector
            ans.push_back(sum);
            return;
        }
        // Recursively include the current element in the sum
        func(ind + 1, sum + nums[ind], nums, ans); 
        // Recursively exclude the current element from the sum
        func(ind + 1, sum, nums, ans); 
    }

public:
    // Function to generate all subset sums
    vector<int> subsetSums(vector<int>& nums) {
        vector<int> ans; 
        // Start the recursion with index 0 and initial sum 0
        func(0, 0, nums, ans);
        return ans;
    }
};

int main() {
    // Sample input vector
    vector<int> nums = {1, 2, 3};
    
    // Create an object of the Solution class
    Solution sol;
    
    // Call the subsetSums function and store the result
    vector<int> result = sol.subsetSums(nums);
    
    // Print the result
    cout << "Subset sums are: ";
    for (int sum : result) {
        cout << sum << " ";
    }
    cout << endl;

    return 0;
}

OR

class Solution {
public:
    // Helper function to recursively calculate subset sums
    void solve(vector<int>& result, vector<int>& nums, vector<int>& output, int index) {
        // Base Case: If we have processed all elements
        if (index == nums.size()) {
            int sum = 0;
            // Calculate the sum of the current subset
            for (int elm : output) {
                sum += elm;
            }
            // Add the sum of this subset to the result
            result.push_back(sum);
            return;
        }

        // Recursive Case 1: Include the current element in the subset
        output.push_back(nums[index]);      // Add the current element to the subset
        solve(result, nums, output, index + 1); // Recurse to the next element

        // Backtrack: Remove the current element to explore the exclusion case
        output.pop_back();

        // Recursive Case 2: Exclude the current element from the subset
        solve(result, nums, output, index + 1); // Recurse to the next element without the current one
    }

    // Main function to find all subset sums of the input array
    vector<int> subsetSums(vector<int>& nums) {
        vector<int> result;        // To store the sums of all subsets
        vector<int> output;        // Temporary vector to build subsets
        solve(result, nums, output, 0); // Start the recursion from index 0
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(2^N * N): Each element has two possibilities (include or exclude), resulting in 2^n combinations.
• Space Complexity: O(N): The space needed to store all possible subset sums and the call stack in recursion can be up to 2^n.