#### 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:

- current elt too large. Skip.
- 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.