LeetCode 416.Partition Equal Subset Sum

# LeetCode 416.Partition Equal Subset Sum

Given a **non-empty** array containing **only positive integers**, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

- Each of the array element will not exceed 100.
- The array size will not exceed 200.

This can be regarded as finding a subset whose sum is equal to a specified number (half of the sum here).

1 | class Solution: |

# LeetCode 494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

1 | Examples: |

This can be converted to a `subset sum`

problem:

Let $P$ and $N$ denote positive subset and negative subset,

So the original problem has been converted to a subset sum problem as follows:

Find a subset P of nums such that `sum(P) = (target + sum(nums)) / 2`

1 | class Solution(object): |