Subset Sum

Medium15–20 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftGoogle

Given an array of non-negative integers and a target amount, determine whether any subset of the array — any selection of its elements, in any combination, each used at most once — adds up to exactly that target. The subset doesn't need to be contiguous, and the empty subset always sums to 0. Every element only ever faces one decision: it's either part of the chosen subset or it isn't. Skipping it leaves the target unchanged for the rest of the array to solve; taking it lowers the target by that element's value for the rest of the array to solve. A target of exactly 0 at any point means a valid subset has already been assembled. Because each element is considered once and only ever shrinks the remaining target (never negative amounts contributing further), the reachable amounts can be tracked directly — building up, one element at a time, the full set of totals that are actually achievable.

Test Case 1:

Input:nums = [2, 3, 4], target = 6

Output:true

Explanation:The subset {2, 4} sums to exactly 6.

Test Case 2:

Input:nums = [2, 7, 11, 4], target = 13

Output:true

Explanation:The subset {2, 11} sums to exactly 13.

Test Case 3:

Input:nums = [3, 7, 5], target = 1

Output:false

Explanation:No combination of 3, 7, and 5 can ever sum to 1 — every non-empty subset totals at least 3.

Constraints

◆1 ≤ nums.length ≤ 20
◆0 ≤ nums[i] ≤ 100
◆0 ≤ target ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

At every number, there are exactly two choices: leave it out of the subset, or include it and subtract its value from the amount still needed. Either choice is worth exploring, since only one of them might eventually lead to a remaining amount of exactly zero — the signal that a valid subset has been found. Running out of numbers before reaching zero, or going negative by including a number that's too large, both mean that particular path fails. Trying every combination of include/exclude decisions answers the question, though the same (index, remaining) situation can be revisited many times along different paths.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;

    public boolean subsetSum(int[] nums, int target) {
        this.nums = nums;
        return solve(0, target);
    }

    private boolean solve(int i, int remaining) {
        if (remaining == 0) return true;
        if (i == nums.length || remaining < 0) return false;
        return solve(i + 1, remaining) || solve(i + 1, remaining - nums[i]);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for every amount from 0 up to target, whether some subset of the numbers seen so far can reach it exactly — a single boolean array indexed by amount. Amount 0 is always reachable (the empty subset), and each number, in turn, can extend any amount that was already reachable before it by that number's value. Sweeping each number's inner update from target down to the number's own value guarantees that number is only ever counted once per amount (using the array's state from before this number was considered), which is exactly what "subset" — as opposed to reusing a number — requires. After every number has been swept through, the entry at target holds the final answer.

TimeO(n × target)

SpaceO(target)