Subset Sum Problem Medium 0 attempts
GeeksforGeeks ↗

Subset Sum Problem

Medium BacktrackingRecursion GeeksforGeeks

You're given an array of non-negative integers and a target value sum. Decide whether some subset of the array's elements adds up to exactly sum, and return true or false accordingly.

Edge cases: A target of sum = 0 is always achievable with the empty subset. Consider arrays with a single matching element, or where every element exceeds sum.

Input Format
Implement isSubsetSum(arr, sum). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
arr = [1,2]
sum = 0
Output
true
Constraints
  • 1 <= arr.length <= 100
  • 0 <= arr[i] <= 10^4
  • 0 <= sum <= 10^5
Test Cases (2)
Case 1
Args: [[3,34,4,12,5,2],9] Expected: true
Case 2
Args: [[1,2],0] Expected: true
Topics
BacktrackingRecursion

Approach: Dynamic Programming

Build a boolean DP table where dp[j] indicates whether a subset summing to j is achievable. For each number in the array, iterate backwards through the table to avoid using the same element twice.

javascript
function isSubsetSum(arr, sum) {
  const dp = new Array(sum + 1).fill(false);
  dp[0] = true;

  for (const num of arr) {
    for (let j = sum; j >= num; j--) {
      if (dp[j - num]) dp[j] = true;
    }
  }
  return dp[sum];
}

Time Complexity: O(n × sum)

Space Complexity: O(sum)

Saved in this browser only. Private to you.

JavaScript