Subset sum — does any subset add up to the target?

Medium

Problem

Given non-negative integers and a target sum, return true if some subset of them adds up exactly to the target.

Example 1

Input:  arr = [3, 34, 4, 12, 5, 2], sum = 9
Output: true

4 + 5.

Example 2

Input:  same, sum = 30
Output: false

Also asked as: Subset Sum Problem · Partition of a set intoK subsets with equal sum · Tug of War

Test cases

Case 1

Input:    [3,34,4,12,5,2], 9
Expected: true

Case 2

Input:    [3,34,4,12,5,2], 30
Expected: false

Case 3

Input:    [5], 5
Expected: true

Case 4

Input:    [1,2], 4
Expected: false

Case 5

Input:    [], 0
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Include / exclude with pruning

Time O(2ⁿ)Space O(n)

At each index either take the number (if it fits) or skip it. Prune when the remaining sum cannot reach the target.

function subsetSum(nums, target) {
const bt = (i, remaining) => {
if (remaining === 0) return true;
if (i === nums.length || remaining < 0) return false;
return bt(i + 1, remaining - nums[i]) || bt(i + 1, remaining);
};
return bt(0, target);
}

Partition into k equal-sum subsets: check total % k === 0, then try to fill k buckets to total/k with backtracking (sort desc, skip duplicate bucket states). Tug of War: split into two halves of size n/2 minimising the sum difference.