Subset summation

You are in a phone screen with Amazon and the interviewer asks: "Given a list of positive integers and a target, can you pick a subset that sums exactly to the target?" This is the Subset Sum problem, one of the most important recursion problems in interview prep. It teaches the include/exclude pattern that shows up in knapsack, combination sum, and dozens of other backtracking questions.

TL;DR

For each element, recursively try two options: include it (subtract from target) or exclude it (keep target). If the target reaches 0, a valid subset exists. If you exhaust all elements without hitting 0, return false. This runs in O(2^n) time and O(n) space.

Why This Problem Matters

The subset sum problem is the gateway to an entire family of interview questions. The include/exclude recursion pattern you learn here is the same pattern used in the 0/1 knapsack problem, partition equal subset sum, combination sum, and target sum. Master this pattern and those problems become variations rather than new challenges.

Understanding the Problem

Given a list of positive integers and a target integer, determine whether any subset of the list sums to the target.

subsetSum([1,2,3], 0) -> true   (empty subset)
subsetSum([1,2,3], 1) -> true   (subset {1})
subsetSum([1,2,3], 3) -> true   (subsets {1,2} or {3})
subsetSum([1,2,3], 5) -> true   (subset {2,3})
subsetSum([1,2,3], 7) -> false  (max sum is 6)

Constraints

• All integers are positive (between 1 and 1000)
• The list has at most 30 elements
• The target is between 0 and 1000

Edge Cases

1. Target is 0: Always true. The empty subset sums to 0.
2. Single element equals target: True.
3. Target exceeds total sum: Always false. No subset can reach it.

Solution Approach

The key insight is that for every element in the array, you have exactly two choices: include it in the subset or leave it out. This maps perfectly to a binary recursion tree.

Define a helper function search(index, arr, target) that:

• Returns true if target == 0 (we found a valid subset)
• Returns false if index == arr.length (no more elements to try)
• Otherwise, recursively tries both including and excluding the current element

Here is how the decision flows for subsetSum([1,2,3], 3), following the path that includes 1 and 2:

We include 1 (target drops to 2), then include 2 (target drops to 0). Since target == 0, we return true immediately without needing to look at the remaining elements.

Now compare with subsetSum([1,2,3], 7), which fails:

Even including every element only reaches 6. Every branch of the recursion tree returns false.

The Full Recursion Tree

For subsetSum([1,2,3], 3), the complete recursion tree shows every branch the algorithm explores. At each node, the left child includes the current element and the right child excludes it. Highlighted nodes are where target == 0:

Notice that the algorithm finds target == 0 at two different nodes: once by including 2 and once by including 3 alone. Thanks to short-circuit evaluation with ||, the algorithm returns true as soon as it finds the first successful path.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public Boolean subsetSum(int[] arr, int target) {
    return search(0, arr, target);
  }

  private boolean search(int index, int[] arr, int target) {
    if (target == 0) return true;
    else if (index == arr.length) return false;
    else return search(index + 1, arr, target - arr[index]) ||
                  search(index + 1, arr, target);
  }
}

Let's walk through the code:

1. Entry point: subsetSum delegates to the recursive search helper starting at index 0
2. Base case 1: If target == 0, we have found a subset that sums to the original target. Return true.
3. Base case 2: If index == arr.length, we have exhausted all elements without finding a valid subset. Return false.
4. Recursive case: Try including arr[index] (subtract it from target) OR excluding it (pass target unchanged). The || operator short-circuits: if the include path returns true, the exclude path is never explored.

Complexity Analysis

Time: O(2^n) where n is the length of the array. Each element creates two recursive branches (include or exclude), forming a binary tree with up to 2^n leaf nodes. In practice, short-circuit evaluation prunes branches once a solution is found, but the worst case (no valid subset) explores the entire tree.

Space: O(n) for the recursion call stack. The maximum recursion depth equals the number of elements, since each call advances the index by one. No additional data structures are allocated.

Can We Do Better?

Yes. Dynamic programming reduces the time to O(n * target) by avoiding redundant subproblems. Build a boolean table dp[i][s] that records whether a subset of the first i elements can sum to s. However, interviewers typically want to see the recursive approach first. Mention the DP optimization as a follow-up if asked.

Common Pitfalls

1. Forgetting the target == 0 base case: Without this check, the algorithm never recognizes a valid subset and always returns false after exhausting elements.

2. Checking target == 0 after the index bounds check: If you check index == arr.length first, you will miss the case where the last element perfectly completes the target. Always check target == 0 first.

3. Modifying the array instead of passing a reduced target: Some candidates try to remove elements from the array. This is error-prone and unnecessary. Passing target - arr[index] is cleaner and avoids mutation bugs.

4. Not handling target 0 as a valid input: subsetSum([1,2,3], 0) should return true. The empty subset has a sum of 0, and the target == 0 base case handles this correctly on the very first call.

Interview Tips

When presenting this solution:

• Clarify the constraints: Are elements positive? Can we reuse elements? (No to reuse; that would be combination sum.)
• Draw the recursion tree for a small example like [1,2,3] with target 3. Label each node with the index and remaining target.
• Explain the include/exclude pattern by name. Interviewers recognize this as the foundation for knapsack and related problems.
• Mention the O(2^n) time complexity upfront. If the interviewer asks for optimization, transition to the DP approach with an O(n * target) table.
• Note that short-circuit evaluation with || means the algorithm stops exploring as soon as it finds a valid subset.

Key Takeaways

• The include/exclude pattern is the core technique: at each element, try both including it (subtract from target) and excluding it (keep target unchanged).
• Two base cases drive the recursion: target == 0 means success, index == arr.length means failure.
• The time complexity is O(2^n) because each element doubles the search space. Space is O(n) from the call stack depth.
• Always check target == 0 before checking the index bounds. The order of base cases matters.
• This same pattern generalizes to 0/1 knapsack, partition equal subset sum, and combination sum problems. Learning it here pays dividends across many interview topics.

Practice and Related Problems

Once you are comfortable with subset sum, try these progressions:

• Combination sum (allow element reuse, return all valid combinations)
• Partition equal subset sum (can you split the array into two subsets with equal sums?)
• 0/1 knapsack (maximize value with a weight constraint)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you are warming up for phone screens or preparing for on-site interviews, mastering recursion patterns like include/exclude sets you up well.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def subset_sum(self, arr: List[int], target: int) -> bool:
        return self.search(0, arr, target)

    def search(self, index: int, arr: List[int], target: int) -> bool:
        if target == 0:
            return True
        elif index == len(arr):
            return False
        else:
            return self.search(index + 1, arr, target - arr[index]) or \
                   self.search(index + 1, arr, target)

JavaScript

class Solution {
  subsetSum(arr, target) {
    return this.search(0, arr, target);
  }

  search(index, arr, target) {
    if (target === 0) return true;
    else if (index === arr.length) return false;
    else return this.search(index + 1, arr, target - arr[index]) ||
        this.search(index + 1, arr, target);
  }
}

TypeScript

class Solution {
  subsetSum(arr: number[], target: number): boolean {
    return this.search(0, arr, target);
  }

  private search(index: number, arr: number[], target: number): boolean {
    if (target === 0) return true;
    else if (index === arr.length) return false;
    else return this.search(index + 1, arr, target - arr[index]) ||
        this.search(index + 1, arr, target);
  }
}

C++

#include <iostream>
#include <vector>

class Solution {
public:
  bool subsetSum(std::vector<int> &arr, int target) {
    return search(0, arr, target);
  }

private:
  bool search(int index, std::vector<int> &arr, int target) {
    if (target == 0) {
      return true;
    } else if (index == arr.size()) {
      return false;
    } else {
      return search(index + 1,
                    arr,
                    target - arr[index]) || search(index + 1, arr, target);
    }
  }
};

Go

package solution

func (s *Solution) SubsetSum(arr []int, target int) bool {
	return search(0, arr, target)
}

func search(index int, arr []int, target int) bool {
	if target == 0 {
		return true
	} else if index == len(arr) {
		return false
	} else {
		return search(index+1, arr, target-arr[index]) || search(index+1, arr, target)
	}
}

type Solution struct {
}

Scala

class Solution {
  def subsetSum(arr: Array[Int], target: Int): Boolean = {
    search(0, arr, target)
  }

  private def search(index: Int, arr: Array[Int], target: Int): Boolean = {
    if (target == 0) true
    else if (index == arr.length) false
    else search(index + 1, arr, target - arr(index)) ||
      search(index + 1, arr, target)
  }
}

Kotlin

class Solution {
  fun subsetSum(arr: IntArray, target: Int): Boolean {
    return search(0, arr, target)
  }

  private fun search(index: Int, arr: IntArray, target: Int): Boolean {
    if (target == 0) return true
    else if (index == arr.size) return false
    else return search(index + 1, arr, target - arr[index]) ||
                  search(index + 1, arr, target)
  }
}

Swift

class Solution {
    func subsetSum(_ arr: [Int], _ target: Int) -> Bool {
        return search(0, arr, target)
    }

    private func search(_ index: Int, _ arr: [Int], _ target: Int) -> Bool {
        if target == 0 { return true }
        else if index == arr.count { return false }
        else { return search(index + 1, arr, target - arr[index]) ||
                      search(index + 1, arr, target) }
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn subset_sum(&self, arr: Vec<i32>, target: i32) -> bool {
        self.search(0, &arr, target)
    }

    fn search(&self, index: usize, arr: &[i32], target: i32) -> bool {
        if target == 0 {
            return true;
        }
        if index == arr.len() {
            return false;
        }
        self.search(index + 1, arr, target - arr[index]) || self.search(index + 1, arr, target)
    }
}

C#

public class Solution {
    public bool SubsetSum(int[] arr, int target) {
        return Search(0, arr, target);
    }

    private bool Search(int index, int[] arr, int target) {
        if (target == 0) return true;
        else if (index == arr.Length) return false;
        else return Search(index + 1, arr, target - arr[index]) ||
                      Search(index + 1, arr, target);
    }
}

Dart

class Solution {
  bool subsetSum(List<int> arr, int target) {
    return _search(0, arr, target);
  }

  bool _search(int index, List<int> arr, int target) {
    if (target == 0) return true;
    else if (index == arr.length) return false;
    else return _search(index + 1, arr, target - arr[index]) ||
                  _search(index + 1, arr, target);
  }
}

PHP

<?php

class Solution {
    public function subsetSum(array $arr, int $target): bool {
        return $this->search(0, $arr, $target);
    }

    private function search(int $index, array $arr, int $target): bool {
        if ($target === 0) return true;
        elseif ($index === count($arr)) return false;
        else return $this->search($index + 1, $arr, $target - $arr[$index]) ||
                    $this->search($index + 1, $arr, $target);
    }
}

Ruby

class Solution
  def subset_sum(arr, target)
    search(0, arr, target)
  end

  def search(index, arr, target)
    return true if target == 0
    return false if index == arr.length
    search(index + 1, arr, target - arr[index]) || search(index + 1, arr, target)
  end
end