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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Microsoft, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 2001 <= arr[i] <= 2001 <= target <= 4 * 10^4
Hints for Subset Sum Problem
Hint 1
Trying all
2^nsubsets is hopeless for 200 elements — but the sums involved are small.Hint 2
Track which totals are reachable. Start with only
0reachable; each elementamakess + areachable for everysalready reachable.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
- Create
can[0..target]with onlycan[0] = true(the empty subset). - For each element
a, forsfromtargetdown toa: ifcan[s - a]is true, setcan[s] = true. - 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
supward lets one element be added repeatedly (that is the unbounded version). - Elements larger than
targetcan simply be skipped. - A quick exit: if the whole array sums to less than
target, the answer isfalse.
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 == 1Java
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