Python – Subset Sum Problem

Python – Subset Sum Problem

The Subset Sum Problem is a classic challenge in computer science and dynamic programming. Given an array of integers and a target sum, the goal is to determine whether there exists a subset of the array that sums exactly to the target.

This tutorial will explain the problem, provide sample inputs and outputs, and present two dynamic programming solutions: one using recursion with memoization and another using an iterative bottom-up approach.

Problem Statement

Given an array arr of integers and an integer target, determine if there is a subset of arr whose sum is equal to target. If such a subset exists, return True; otherwise, return False.

Sample Input and Output

Example 1:

# Input:
arr = [3, 34, 4, 12, 5, 2]
target = 9

# Output:
True

Explanation: In this example, the subset [4, 5] (among other possible combinations, e.g., [3, 4, 2]) sums to 9. Thus, the function returns True.

Example 2:

# Input:
arr = [1, 2, 7, 1, 5]
target = 10

# Output:
False

Explanation: In this example, no subset of the array [1, 2, 7, 1, 5] can be found that sums to 10. Therefore, the function returns False.

Solution Approach

The Subset Sum Problem can be solved using dynamic programming by breaking the problem into smaller subproblems. The idea is to build a table (or use recursion) that tracks whether a sum j can be achieved with the first i elements of the array.

For the iterative approach, we create a 2D DP table dp[i][j] where:

1. Base Case: dp[0][0] = True (a sum of 0 is always possible with 0 elements) and for all j > 0, dp[0][j] = False (no sum can be formed with 0 elements).
2. Recurrence Relation: For each element arr[i-1] and each target sum j:
   • If arr[i-1] > j, then dp[i][j] = dp[i-1][j] (we cannot include the current element).
   • If arr[i-1] ≤ j, then dp[i][j] = dp[i-1][j] or dp[i-1][j - arr[i-1]] (either exclude or include the current element).

An alternative approach is to use recursion with memoization, where the problem is solved by exploring two possibilities for each element (include or exclude) and caching intermediate results to improve efficiency.

Python Program

Method 1: Recursive Approach with Memoization

def subset_sum_recursive(arr, target, index=0, memo=None):
    """
    Determine if there is a subset of 'arr' that sums to 'target' using recursion with memoization.
    
    Parameters:
    arr (list): List of integers.
    target (int): The target sum to achieve.
    index (int): Current index in the array.
    memo (dict): Cache to store computed results for (index, target) pairs.
    
    Returns:
    bool: True if a subset exists that sums to 'target', otherwise False.
    """
    if memo is None:
        memo = {}
    
    # Base cases
    if target == 0:
        return True
    if index >= len(arr):
        return False
    
    # Check if the result is already computed
    if (index, target) in memo:
        return memo[(index, target)]
    
    # If current element is greater than the target, skip it
    if arr[index] > target:
        result = subset_sum_recursive(arr, target, index + 1, memo)
    else:
        # Explore both possibilities: include or exclude the current element
        result = (subset_sum_recursive(arr, target - arr[index], index + 1, memo) or 
                  subset_sum_recursive(arr, target, index + 1, memo))
    
    memo[(index, target)] = result
    return result

# Test examples for Recursive Approach
print("Method 1 - Recursive with Memoization")
print("Subset sum for [3, 34, 4, 12, 5, 2] with target 9:", subset_sum_recursive([3, 34, 4, 12, 5, 2], 9))   # Expected: True
print("Subset sum for [1, 2, 7, 1, 5] with target 10:", subset_sum_recursive([1, 2, 7, 1, 5], 10))       # Expected: False

Explanation: This recursive method examines each element with two choices: include it (reducing the target by the element’s value) or exclude it (leaving the target unchanged). The memoization dictionary memo caches the results for each (index, target) pair to prevent redundant calculations.

Method 2: Iterative Dynamic Programming

def subset_sum_iterative(arr, target):
    """
    Determine if there is a subset of 'arr' that sums to 'target' using an iterative dynamic programming approach.
    
    Parameters:
    arr (list): List of integers.
    target (int): The target sum to achieve.
    
    Returns:
    bool: True if a subset exists that sums to 'target', otherwise False.
    """
    n = len(arr)
    # Create a DP table with dimensions (n+1) x (target+1)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    
    # Base case: A sum of 0 is always achievable (by choosing no elements)
    for i in range(n + 1):
        dp[i][0] = True
        
    # Fill the DP table
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if arr[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]
    
    return dp[n][target]

# Test examples for Iterative DP Approach
print("\nMethod 2 - Iterative Dynamic Programming")
print("Subset sum for [3, 34, 4, 12, 5, 2] with target 9:", subset_sum_iterative([3, 34, 4, 12, 5, 2], 9))   # Expected: True
print("Subset sum for [1, 2, 7, 1, 5] with target 10:", subset_sum_iterative([1, 2, 7, 1, 5], 10))       # Expected: False

Explanation: The iterative approach builds a 2D table dp where each entry dp[i][j] is True if a subset of the first i elements can achieve the sum j. The table is initialized with the fact that a sum of 0 is always possible, and then it is filled using the decision of whether to include the current element or not.

Conclusion

In this tutorial, we explored two dynamic programming approaches to solve the Subset Sum Problem:

1. Recursive with Memoization: This method recursively explores including or excluding each element and caches results to enhance performance.
2. Iterative Dynamic Programming: This approach constructs a DP table to determine if a subset exists that sums to the target value.

Both methods provide effective solutions to the Subset Sum Problem. The choice between them depends on the problem constraints and input size. Happy coding!