BackTrackingProblem 8 of 19

Subset Sum Problem

Brute Force
Time: O(2^n)
Space: O(n)
Optimal
Time: O(n × sum)
Space: O(sum)

Problem Statement

Given a set of non-negative integers and a target sum, determine if there exists a subset whose sum equals the target. Also, find all such subsets.

Example:

Input: arr = [3, 34, 4, 12, 5, 2], target = 9 Output: true Explanation: Subset [4, 5] sums to 9 Input: arr = [3, 34, 4, 12, 5, 2], target = 30 Output: false Explanation: No subset sums to 30

Approach 1: Brute Force (Backtracking)

Intuition

Explore all possible subsets by either including or excluding each element. Track the current sum and check if it equals the target.

Algorithm

  1. For each element, we have two choices: include or exclude
  2. Track current sum as we go
  3. If sum equals target, we found a valid subset
  4. Use backtracking to explore all possibilities
java
import java.util.*;

class Solution {
    public boolean solve(int[] arr, int index, int target, int currentSum) {
        // Found the target sum
        if (currentSum == target) {
            return true;
        }
        
        // Base cases
        if (index >= arr.length || currentSum > target) {
            return false;
        }
        
        // Include current element
        if (solve(arr, index + 1, target, currentSum + arr[index])) {
            return true;
        }
        
        // Exclude current element
        if (solve(arr, index + 1, target, currentSum)) {
            return true;
        }
        
        return false;
    }
    
    public boolean isSubsetSum(int[] arr, int target) {
        return solve(arr, 0, target, 0);
    }
    
    // Find all subsets with given sum
    public void findAllSubsets(int[] arr, int index, int target, int currentSum,
                               List<Integer> current, List<List<Integer>> result) {
        if (currentSum == target) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        if (index >= arr.length || currentSum > target) {
            return;
        }
        
        // Include current element
        current.add(arr[index]);
        findAllSubsets(arr, index + 1, target, currentSum + arr[index], current, result);
        current.remove(current.size() - 1);
        
        // Exclude current element
        findAllSubsets(arr, index + 1, target, currentSum, current, result);
    }
}

Complexity Analysis

  • Time Complexity: O(2^n) - Two choices for each element
  • Space Complexity: O(n) - Recursion stack

Approach 2: Optimal (Dynamic Programming)

Intuition

Use DP where dp[i][j] represents whether it's possible to achieve sum j using the first i elements. This avoids redundant computation.

Algorithm

  1. Create DP table of size (n+1) × (target+1)
  2. dp[i][0] = true (empty subset sums to 0)
  3. dp[0][j] = false for j > 0 (no elements, can't achieve positive sum)
  4. dp[i][j] = dp[i-1][j] || dp[i-1][j-arr[i-1]]
java
import java.util.*;

class Solution {
    public boolean isSubsetSum(int[] arr, int target) {
        int n = arr.length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        
        // Empty subset can achieve sum 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        
        // Fill the DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                // Don't include current element
                dp[i][j] = dp[i - 1][j];
                
                // Include current element (if possible)
                if (j >= arr[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i - 1]];
                }
            }
        }
        
        return dp[n][target];
    }
    
    // Space optimized version
    public boolean isSubsetSumOptimized(int[] arr, int target) {
        int n = arr.length;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        
        for (int i = 0; i < n; i++) {
            // Traverse from right to left
            for (int j = target; j >= arr[i]; j--) {
                dp[j] = dp[j] || dp[j - arr[i]];
            }
        }
        
        return dp[target];
    }
}

Complexity Analysis

  • Time Complexity: O(n × target) - Fill the DP table
  • Space Complexity: O(target) - Optimized 1D DP

Approach 3: Print All Subsets with Given Sum

Intuition

Combine backtracking to enumerate all subsets while tracking the current sum and current elements.

java
import java.util.*;

class Solution {
    public void printSubsets(int[] arr, int index, int target,
                             List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        if (index >= arr.length || target < 0) {
            return;
        }
        
        // Include current element
        current.add(arr[index]);
        printSubsets(arr, index + 1, target - arr[index], current, result);
        current.remove(current.size() - 1);
        
        // Exclude current element (skip duplicates)
        while (index + 1 < arr.length && arr[index] == arr[index + 1]) {
            index++;
        }
        printSubsets(arr, index + 1, target, current, result);
    }
    
    public List<List<Integer>> findSubsets(int[] arr, int target) {
        Arrays.sort(arr);  // Sort to handle duplicates
        List<List<Integer>> result = new ArrayList<>();
        printSubsets(arr, 0, target, new ArrayList<>(), result);
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(2^n) - Enumerate all subsets
  • Space Complexity: O(n) - Recursion depth

Key Takeaways

  1. Include/Exclude Pattern: Classic backtracking decision at each element
  2. DP Optimization: Converts exponential to pseudo-polynomial time
  3. Space Optimization: 1D DP by traversing right to left
  4. Duplicate Handling: Sort array and skip consecutive duplicates
  5. 0/1 Knapsack: Subset Sum is a special case of 0/1 Knapsack
  6. NP-Complete: The decision problem is NP-complete
Previous
Print all palindromic partitions of a string
Next
The Knights tour problem