Subset Sum Problem

Algorithms

The Subset Sum problem determines whether there exists a subset of a given set of integers that sums to a target value.

Problem Statement

Given a set of integers and a target sum, determine if there exists a subset whose elements sum to the target.

Dynamic Programming Solution

We use dynamic programming where $d p [i] [j]$ is $True$ if there exists a subset of the first $i$ elements that sums to $j$ .

Time Complexity

The time complexity is $O (n \times t a r g e t)$ , where $n$ is the number of elements.

Implementation

def subset_sum(arr, target):
    """Dynamic Programming approach to solve the Subset Sum Problem."""
    n = len(arr)
    
    # Initialize dp table
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    
    # A sum of 0 can always be achieved with an empty subset
    for i in range(n + 1):
        dp[i][0] = True
    
    # Fill dp table
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if j >= arr[i-1]:
                dp[i][j] = dp[i-1][j] or dp[i-1][j - arr[i-1]]
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[n][target]

# Example usage:
arr = [3, 34, 4, 12, 5, 2]
target = 9
print("Is there a subset with sum {}? {}".format(target, subset_sum(arr, target)))  # Output: True