Subset sum — does any subset add up to the target?
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
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.