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.
- 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).
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.
- Input: nums is [1, 1, 1, 1, 1], S is 3.
- Output: 5
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
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