# 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[i] = False
for i in range(len(my_set) + 1):
dp[i] = 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.