Problem Statement #

Write a function subsetSum that takes an array of integers and a target number. The function should return true if there exists a subset of the array that sums up to the target, and false otherwise.

Important Notes:

• A subset can be any size (from 0 elements to all elements)
• Elements do not need to be consecutive in the array
• Each element can only be used once
• The array can contain negative numbers

Examples #

subsetSum([3, 7, 4, 2], 5)           // true (3 + 2 = 5)
subsetSum([3, 34, 4, 12, 5, 12], 32) // true (3 + 12 + 5 + 12 = 32)
subsetSum([8, 2, 4, 12], 13)         // false
subsetSum([8, -2, 1, -3], 6)         // true (8 + 1 + (-3) = 6)

Understanding the Problem #

The subset sum problem is a classic dynamic programming and recursion problem. At each position in the array, we face a decision: include the current element in our subset or exclude it. This binary choice at each step creates a decision tree that we can explore recursively.

Why This Problem is Important #

The subset sum problem is:

• A fundamental problem in computer science and complexity theory
• NP-complete in its general form
• A building block for understanding more complex problems like the knapsack problem
• An excellent introduction to dynamic programming concepts

Approach 1: Recursive Solution #

The recursive approach is the most intuitive way to think about this problem. We explore all possible subsets by making a binary choice at each element.

Recursive Implementation #

function subsetSum(arr, target, index = 0) {
  // Base case 1: Target reached
  if (target === 0) {
    return true;
  }
  
  // Base case 2: End of array reached
  if (index >= arr.length) {
    return false;
  }
  
  // Recursive case: Try including current element OR excluding it
  const includeCurrentElement = subsetSum(arr, target - arr[index], index + 1);
  const excludeCurrentElement = subsetSum(arr, target, index + 1);
  
  return includeCurrentElement || excludeCurrentElement;
}

How the Recursion Works #

Base Cases:

1. Target is 0: We’ve successfully found a subset that sums to the target. Return true.

2. Index out of bounds: We’ve exhausted all elements without reaching the target. Return false.

Recursive Case:

At each position, we branch into two recursive calls:

1. Include current element: Subtract arr[index] from the target and move to the next index
2. Exclude current element: Keep the target the same and move to the next index

If either branch returns true, we’ve found a valid subset.

Visualization Example #

Let’s trace through subsetSum([3, 7, 4, 2], 5):

                        subsetSum([3,7,4,2], 5, 0)
                       /                          \
            include 3 /                            \ exclude 3
                     /                              \
        subsetSum([...], 2, 1)              subsetSum([...], 5, 1)
           /              \                     /              \
    include 7/        exclude 7\         include 7/        exclude 7\
         /                  \               /                  \
    SS([],-5,2)         SS([],2,2)     SS([],-2,2)         SS([],5,2)
                           /    \                             /    \
                     include 4  exclude 4              include 4  exclude 4
                         /          \                     /          \
                    SS([],-2,3)  SS([],2,3)          SS([],1,3)   SS([],5,3)
                                    /    \                /   \        /    \
                              include 2  exclude 2   include 2  ...   ...  ...
                                 /          \           /
                            SS([],0,4)  SS([],2,4)  SS([],-1,4)
                              ✓ TRUE      FALSE        FALSE

The path [3, exclude 7, exclude 4, 2] gives us 3 + 2 = 5, returning true.

Time and Space Complexity #

Time Complexity: O(2^n) where n is the length of the array

• At each element, we make 2 choices (include or exclude)
• This creates a binary tree of depth n
• Total nodes in the tree: 2^n

Space Complexity: O(n) for the recursion call stack

• Maximum depth of recursion is n (length of array)
• Each recursive call adds a frame to the call stack

Approach 2: Dynamic Programming (Memoization) #

The recursive solution has overlapping subproblems. We can optimize it using memoization to avoid recalculating the same subproblems.

Memoized Solution #

function subsetSumMemo(arr, target) {
  const memo = new Map();
  
  function helper(index, currentTarget) {
    // Create unique key for this subproblem
    const key = `${index}-${currentTarget}`;
    
    // Check if we've already solved this subproblem
    if (memo.has(key)) {
      return memo.get(key);
    }
    
    // Base cases
    if (currentTarget === 0) {
      return true;
    }
    
    if (index >= arr.length) {
      return false;
    }
    
    // Recursive case with memoization
    const includeElement = helper(index + 1, currentTarget - arr[index]);
    const excludeElement = helper(index + 1, currentTarget);
    
    const result = includeElement || excludeElement;
    memo.set(key, result);
    
    return result;
  }
  
  return helper(0, target);
}

Time and Space Complexity (Memoized) #

Time Complexity: O(n × sum) where n is array length and sum is the target

• Each unique (index, target) pair is calculated only once
• Maximum unique states: n × sum

Space Complexity: O(n × sum)

• Memoization table stores results for each unique state
• Call stack depth is still O(n)

Approach 3: Dynamic Programming (Tabulation) #

We can also solve this problem bottom-up using a 2D table.

Tabulation Solution #

function subsetSumDP(arr, target) {
  const n = arr.length;
  
  // Handle negative targets by shifting
  const offset = Math.abs(Math.min(...arr, 0)) * n;
  const shiftedTarget = target + offset;
  const maxSum = Math.abs(Math.max(...arr, 0)) * n + offset;
  
  // Create DP table: dp[i][j] = can we make sum j using first i elements
  const dp = Array(n + 1).fill(null).map(() => 
    Array(maxSum + 1).fill(false)
  );
  
  // Base case: sum of 0 is always achievable (empty subset)
  for (let i = 0; i <= n; i++) {
    dp[i][offset] = true;
  }
  
  // Fill the table
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= maxSum; j++) {
      // Exclude current element
      dp[i][j] = dp[i - 1][j];
      
      // Include current element (if valid)
      const prevSum = j - arr[i - 1];
      if (prevSum >= 0 && prevSum <= maxSum) {
        dp[i][j] = dp[i][j] || dp[i - 1][prevSum];
      }
    }
  }
  
  return dp[n][shiftedTarget] || false;
}

Approach 4: Backtracking with Path Tracking #

If you need to know which elements form the subset, use backtracking:

function subsetSumWithPath(arr, target) {
  const result = { found: false, path: [] };
  
  function backtrack(index, currentTarget, path) {
    if (currentTarget === 0) {
      result.found = true;
      result.path = [...path];
      return true;
    }
    
    if (index >= arr.length) {
      return false;
    }
    
    // Try including current element
    path.push(arr[index]);
    if (backtrack(index + 1, currentTarget - arr[index], path)) {
      return true;
    }
    path.pop();
    
    // Try excluding current element
    if (backtrack(index + 1, currentTarget, path)) {
      return true;
    }
    
    return false;
  }
  
  backtrack(0, target, []);
  return result;
}

// Example usage:
const result = subsetSumWithPath([3, 7, 4, 2], 5);
console.log(result); // { found: true, path: [3, 2] }

Common Pitfalls and Edge Cases #

Edge Cases to Consider #

1. Empty array: subsetSum([], 5) should return false
2. Target is 0: subsetSum([1, 2, 3], 0) should return true (empty subset)
3. Negative numbers: subsetSum([8, -2, 1, -3], 6) must handle negatives correctly
4. All elements needed: subsetSum([1, 2, 3], 6) uses all elements
5. Single element: subsetSum([5], 5) should return true

Common Mistakes #

1. Forgetting the base case where target is 0: This represents the empty subset, which always exists.

2. Incorrect index bounds: Make sure to check index >= arr.length and not index > arr.length.

3. Not handling negative numbers: The simple DP approach needs modification for negative numbers.

4. Modifying the target incorrectly: When including an element, remember to subtract it from the target.

Comparison of Approaches #

Practice Problems #

To solidify your understanding, try these related problems:

1. Subset Sum Count: Return the number of subsets that sum to the target
2. Partition Equal Subset Sum: Can you partition the array into two subsets with equal sum?
3. Target Sum: Assign + or - to each number to reach a target
4. Coin Change: Minimum coins needed to make a target amount

Conclusion #

The subset sum problem demonstrates the power of recursive thinking and dynamic programming. While the recursive solution is intuitive and easy to understand, it’s inefficient for large inputs. Memoization and tabulation provide significant performance improvements by eliminating redundant calculations.

For interviews, start with the recursive solution to show your problem-solving approach, then optimize with memoization if asked. Understanding the trade-offs between different approaches is key to becoming a strong problem solver.