Determining If a Subset of Distinct Integers Sum to a Given Number

Problem

Given a set of distinct integers, write a function that determines whether there is a subset of the integers that sums to a given number.
Example input:
nums = [3, 34, 4, 12, 5, 12]
target = 32
Example output:
True

Solution

This solution is in Python. Our A.I. can create solutions in multiple languages.

kayakane

# Solution:
# This is a dynamic programming problem.
# The solution is to create a 2D array of size (n+1) x (target+1)
# The first row and column are initialized to 0.
# The rest of the cells are filled in using the following logic:
# If the target is 0, then the answer is True.
# If the target is less than 0, then the answer is False.
# If the target is greater than 0, then the answer is True if the answer for the previous target is True, or if the answer for the target minus the current number is True.
# The answer is False otherwise.
# The final answer is in the bottom right cell.

def subset_sum(nums, target):
    n = len(nums)
    dp = [[False for _ in range(target+1)] for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = True
    for i in range(1, n+1):
        for j in range(1, target+1):
            if j < num s[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
    return dp[n][target]

nums = [3, 34, 4, 12, 5, 12]
target = 32
print(subset_sum(nums, target))