Subset Sum Problem Medium 0 attempts
GeeksforGeeks ↗

Subset Sum Problem

Medium BacktrackingRecursion GeeksforGeeks

Given an array of non-negative integers and a target value sum, determine whether any subset of the array adds up to exactly sum. Return true if such a subset exists, false otherwise.

Example 1:

Input: arr = [3, 34, 4, 12, 5, 2], sum = 9
Output: true
Explanation: Subset [4, 5] sums to 9.

Example 2:

Input: arr = [3, 34, 4, 12, 5, 2], sum = 30
Output: false

Edge cases: sum = 0 is always true (empty subset). Array with a single element equal to sum. All elements larger than sum.

Sample Input
nums = [3, 34, 4, 12, 5, 2], sum = 9
Sample Output
true
Constraints
  • 1 <= N <= 100
  • 1 <= arr[i] <= 10^4
  • 1 <= sum <= 10^5
Test Cases
Case 1
Args: [[3,34,4,12,5,2],9] 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.

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