👨‍💻 738LeetCode

Subset Sum

Question

Given a set and a target sum, check if we can find some elts which sum to the target sum.

Example

Input: set = [3,34,4,12,5,2], target sum = 9
Output: True
Input: set = [3,34,4,12,5,2], target sum = 90
Output: False

Solution

Classic DP. Two cases:

  1. current elt too large. Skip.
  2. current elt is included in the subset.

Just note the sum can be 0, so we need an extra row and col.

def checkSubsetSum(my_set, target):
    dp = [[False for i in range(target + 1)] for _ in range(len(my_set) + 1)]
    for i in range(target + 1):
        dp[0][i] = False
    for i in range(len(my_set) + 1):
        dp[i][0] = True
    # Order of eval: left -> right, top -> bottom
    for i in range(1, len(my_set) + 1):
        for j in range(1, target + 1):
            # j is current target sum
            if my_set[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            if my_set[i - 1] <= j:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - my_set[i - 1]]
    return dp[-1][-1]

Comment

I sometimes cannot think of DP array storing True/False instead of elts. If I want to trace elts, using a helper DP table of the same size should do it.