Jaspreet singh

Posted on Jun 16

Subset Sums | Recursion / Backtracking

#algorithms #computerscience #java #tutorial

geeksforgeeks.org

Problem Statement

Given an array arr[] of size N, generate the sum of every possible subset.

Return all subset sums.

Brute Force Intuition

Every element has only two choices:

Include it
Exclude it

For N elements:

2 × 2 × 2 × ... N times

which gives:

2^N subsets

We recursively explore both choices for every element and calculate the sum formed.

Pattern Recognition

Whenever you see:

Generate all subsets
Pick / Not Pick
Every possible combination

Think:

Recursion + Backtracking

Recursive Decision Tree

Example:

arr = [2,3]

                0
           /         \
        +2            skip
       /  \          /   \
    +3   skip     +3   skip

     5     2      3      0

Subset sums:

5 2 3 0

Optimal Java Solution

import java.util.*;

class Solution {

    ArrayList<Integer> subsetSums(int[] arr) {

        ArrayList<Integer> ans = new ArrayList<>();

        solve(0, 0, arr, ans);

        Collections.sort(ans);

        return ans;
    }

    private void solve(int index,
                       int sum,
                       int[] arr,
                       ArrayList<Integer> ans) {

        if (index == arr.length) {
            ans.add(sum);
            return;
        }

        // Pick
        solve(index + 1,
              sum + arr[index],
              arr,
              ans);

        // Not Pick
        solve(index + 1,
              sum,
              arr,
              ans);
    }
}

Dry Run

Input

arr = [1,2]

Recursion

Pick 1
    Pick 2      -> 3
    Skip 2      -> 1

Skip 1
    Pick 2      -> 2
    Skip 2      -> 0

Output

[0,1,2,3]

Why Recursion Works?

For every element we have exactly two choices:

Take it
Don't take it

Exploring both choices guarantees that every subset is generated exactly once.

Complexity Analysis

Metric	Complexity
Time Complexity	O(2^N)
Space Complexity	O(N)

Reason:

2^N subsets exist

and recursion depth is:

Interview One-Liner

For each element, recursively explore both possibilities—pick and not pick. When we reach the end of the array, the accumulated sum represents one subset sum.

Pattern Learned

Generate All Subsets
+
Pick / Not Pick

=> Backtracking
=> Recursion

DEV Community