• 44.2%

https://leetcode.com/problems/target-sum/?tab=Description

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.

Note:

• The length of the given array is positive and will not exceed 20.
• The sum of elements in the given array will not exceed 1000.
• Your output answer is guaranteed to be fitted in a 32-bit integer.

dfs

For example:

Given nums = [1, 2, 3, 4, 5] and target = 3 then one possible solution is +1-2+3-4+5 = 3

Here positive subset is P = [1, 3, 5] and negative subset is N = [2, 4]

Then let’s see how this can be converted to a subset sum problem:

test
sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)
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

Note that the above formula has proved that target + sum(nums) must be even

https://discuss.leetcode.com/topic/76243/java-15-ms-c-3-ms-o-ns-iterative-dp-solution-using-subset-sum-with-explanation

Java (15 ms) C++ (3 ms) O(ns) iterative DP solution using subset sum with explanation

The recursive solution is very slow, because its runtime is exponential

The original problem statement is equivalent to:

Find a subset of nums that need to be positive, and the rest of them negative, such that the sum is equal to target

Let P be the positive subset and N be the negative subset

For example:

Given nums = [1, 2, 3, 4, 5] and target = 3 then one possible solution is +1-2+3-4+5 = 3

Here positive subset is P = [1, 3, 5] and negative subset is N = [2, 4]

Then let’s see how this can be converted to a subset sum problem:

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

Note that the above formula has proved that target + sum(nums) must be even

We can use that fact to quickly identify inputs that do not have a solution (Thanks to @BrunoDeNadaiSarnaglia for the suggestion)

For detailed explanation on how to solve subset sum problem, you may refer to Partition Equal Subset Sum

Here is Java solution (15 ms)

Here is C++ solution (3 ms)

int dp[s + 1] = { 0 }; 上式中=后面是初始化内容，不初始化可能出错。

https://discuss.leetcode.com/topic/76397/c-iterative-with-unordered_map

C++ iterative with unordered_map

https://discuss.leetcode.com/topic/76373/evolve-from-brute-force-to-dp

Evolve from brute force to dp

This is similar to Partition Equal Subset Sum.

1. O(2^n) brute force
1. O(ns) Memoization. There is redundancy in brute force. A call to find with the same start index and target sum can be made multiple times. We can use a 2d table to cache the result to avoid duplicate calls with the same state.
1. O(ns) dp, most dp problems visits continuous states and this is a great example to use hashtable to visit valid states only.
1. O(ns) time, linear space dp.
1. O(ns) dp with continuous states. When hashtable is replaced by vector, test cases show significant runtime improvement. #4 is theoretically better because it does not visit invalid states.

#### python

https://discuss.leetcode.com/topic/76205/python-dp

Python DP

https://discuss.leetcode.com/topic/76650/python-intuitive-dfs-solution-with-memorization

Python intuitive DFS solution with memorization

At first I just remember the current index and current target, and for each index, either subtract the nums[i] from S or add it to S. But this got TLE, them I came up with this solution. Just store the intermediate result with (index, s) and this got accepted.