How to Solve Subset Sum Problems in Python?

Estimated read time 2 min read

The Subset Sum Problem is a combinatorial optimization problem that asks you to find a subset of a given set of integers that sums to a specified target value. Here is an example of how to solve this problem in Python using dynamic programming:

def subset_sum(nums, target):
    n = len(nums)
    # create a 2D array to store the solutions to subproblems
    dp = [[False for j in range(target+1)] for i in range(n+1)]
    # initialize the first row to True (base case)
    for j in range(target+1):
        dp[0][j] = False
    # initialize the first column to True (base case)
    for i in range(n+1):
        dp[i][0] = True
    # fill in the remaining entries of the array using dynamic programming
    for i in range(1, n+1):
        for j in range(1, target+1):
            if nums[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
    # return the solution (True or False)
    return dp[n][target]

# test the function with a sample input
nums = [3, 34, 4, 12, 5, 2]
target = 9
print(subset_sum(nums, target))

In this solution, we define a function subset_sum that takes a list of integers nums and a target value target as input. The function first initializes a 2D array dp to store the solutions to subproblems. The array has n+1 rows and target+1 columns, where n is the length of nums.

The function then initializes the first row of the array to False and the first column of the array to True, which are the base cases of the dynamic programming algorithm.

The function then fills in the remaining entries of the array using dynamic programming. For each entry dp[i][j], the function checks whether including or excluding the i-th element of nums leads to a subset sum of j. If the i-th element is excluded, the solution is dp[i-1][j]. If the i-th element is included, the solution is dp[i-1][j-nums[i-1]]. The function takes the logical OR of these two cases to obtain the solution for dp[i][j].

Finally, the function returns the solution for the original problem, which is stored in dp[n][target].

In the main part of the script, we test the function with a sample input list nums and target value target and print out the result.

To use this code with other inputs, simply replace nums and target with the desired inputs.

You May Also Like

More From Author

+ There are no comments

Add yours

Leave a Reply