Subset Sum Problem

Medium
1604.

Subset Sum Problem

Subset Sum Problem is a medium coding problem on arrays and dynamic programming, asked in Amazon, Microsoft and Adobe interviews.

Given an array of positive integers arr and an integer target, decide whether some subset of arr adds up to exactly target.

A subset may use any selection of the elements (each element at most once, in any order). Return true if such a subset exists, and false otherwise.

Example 1

Input
arr = [3,34,4,12,5,2], target = 9
Output
true
Explanation
4 + 5 = 9.

Example 2

Input
arr = [3,34,4,12,5,2], target = 30
Output
false
Explanation
No selection of these numbers sums to 30.

Example 3

Input
arr = [1,2,3], target = 6
Output
true
Explanation
The whole array is a subset too.

Constraints

  • 1 <= arr.length <= 200
  • 1 <= arr[i] <= 200
  • 1 <= target <= 4 * 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {boolean}
 */
var isSubsetSum = function(arr, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Subset Sum Problem — Solution in Python, Java & C++

Subset Sum Problem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Subset Sum Problem is a medium coding problem on arrays and dynamic programming, asked in Amazon, Microsoft and Adobe interviews.

Problem statement

Given an array of positive integers arr and an integer target, decide whether some subset of arr adds up to exactly target.

A subset may use any selection of the elements (each element at most once, in any order). Return true if such a subset exists, and false otherwise.

Example 1

Input: arr = [3,34,4,12,5,2], target = 9
Output: true
Explanation: 4 + 5 = 9.

Example 2

Input: arr = [3,34,4,12,5,2], target = 30
Output: false
Explanation: No selection of these numbers sums to 30.

Example 3

Input: arr = [1,2,3], target = 6
Output: true
Explanation: The whole array is a subset too.

Constraints

  • 1 <= arr.length <= 200
  • 1 <= arr[i] <= 200
  • 1 <= target <= 4 * 10^4

Hints for Subset Sum Problem

  1. Hint 1

    Trying all 2^n subsets is hopeless for 200 elements — but the sums involved are small.

  2. Hint 2

    Track which totals are reachable. Start with only 0 reachable; each element a makes s + a reachable for every s already reachable.

  3. Hint 3

    Use a boolean array can[0..target] and update it from high to low (can[s] |= can[s - a]) so each element is used at most once.

How to solve Subset Sum Problem

Instead of enumerating subsets, enumerate the sums they can make. After processing a prefix of the array, can[s] says whether some subset of that prefix sums to s; adding an element shifts every reachable sum by its value.

Approach

  1. Create can[0..target] with only can[0] = true (the empty subset).
  2. For each element a, for s from target down to a: if can[s - a] is true, set can[s] = true.
  3. Return can[target].

Why it works

A subset of the first i elements summing to s either avoids element i (so s was reachable before) or uses it (so s - a was reachable before). Scanning s downward guarantees can[s - a] still reflects the state before element i, so no element is counted twice. Sums above target can never come back down, so they are never needed.

Complexity

  • Time — O(n * target)
  • Space — O(target)

Pitfalls

  • Iterating s upward lets one element be added repeatedly (that is the unbounded version).
  • Elements larger than target can simply be skipped.
  • A quick exit: if the whole array sums to less than target, the answer is false.

Reference solution

Python

from typing import List

def isSubsetSum(arr: List[int], target: int) -> bool:
    # Bit s of reach is set when some subset sums to s.
    reach = 1
    mask = (1 << (target + 1)) - 1
    for a in arr:
        reach = (reach | (reach << a)) & mask
    return (reach >> target) & 1 == 1

Java

public static boolean isSubsetSum(int[] arr, int target) {
    boolean[] can = new boolean[target + 1];
    can[0] = true;
    for (int a : arr) {
        for (int s = target; s >= a; s--) {
            if (can[s - a]) can[s] = true;
        }
    }
    return can[target];
}

C++

bool isSubsetSum(vector<int>& arr, int target) {
    vector<char> can(target + 1, 0);
    can[0] = 1;
    for (int a : arr) {
        for (int s = target; s >= a; s--) {
            if (can[s - a]) can[s] = 1;
        }
    }
    return can[target] != 0;
}

JavaScript

var isSubsetSum = function(arr, target) {
    var can = new Array(target + 1).fill(false);
    can[0] = true;
    for (var i = 0; i < arr.length; i++) {
        var a = arr[i];
        for (var s = target; s >= a; s--) {
            if (can[s - a]) can[s] = true;
        }
    }
    return can[target];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming