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

This problem deals with finding a subset of distinct integers that sum to a given number. An example input and output are given.


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:


This solution is in Python. Our A.I. can create solutions in multiple languages.
by 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]
                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))

A.I. Evaluation of the Solution

The candidate's solution is complete and solves the problem. The candidate uses a dynamic programming approach, which is a good approach for this problem.

Evaluated at: 2022-11-21 16:15:37