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 = 20

# Output:
False

Explanation: In this example, no subset of the array [1, 2, 7, 1, 5] can be found that sums to 20. 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 20:", subset_sum_recursive([1, 2, 7, 1, 5], 20))       # 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 20:", subset_sum_iterative([1, 2, 7, 1, 5], 20))       # Expected: False

Explanation:

In the given subset_sum_iterative function, a DP table dp is created with dimensions (n+1) x (target+1), where n is the number of elements in the input list arr and target is the sum we are trying to achieve.

Axes of the DP Table:

Rows (First Index, i)

The rows represent the number of elements considered from the array. Specifically:

• Row 0: No elements are considered.
• Row 1: Only the first element is considered.
• Row 2: The first two elements are considered.
• … and so on up to Row n: All elements are considered.

Columns (Second Index, j)

The columns represent the possible sums from 0 up to the target. Specifically:

• Column 0: Represents a target sum of 0, which is always achievable by selecting no elements.
• Column 1: Represents whether a subset can sum to 1.
• Column 2: Represents whether a subset can sum to 2.
• … and so on up to Column target: Represents whether a subset can sum to the target value.

Interpreting dp[i][j]

Each entry dp[i][j] in the table indicates whether it is possible to achieve the sum j using the first i elements of the array.

Visualization of the DP Axes

If you visualize the DP table:

• x-axis (Rows): Represents the number of elements considered (from 0 to n).
• y-axis (Columns): Represents the target sums (from 0 to target).

This structure allows the algorithm to build the solution gradually. Starting from the base case (a sum of 0 is always achievable), the table is filled by considering whether including or excluding each element allows you to reach each intermediate sum, until the final answer at dp[n][target] is determined.

Debug Screenshots:

For the base case of dp table.

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!