- 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.

1 | Example 1: |

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

我的代码实现：

1 | class Solution { |

方法二:

最核心的是发现其中的规律，找到下面的规律，本题目就和题目416是一样的了。

我的代码实现：

1 | class Solution { |

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

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:

1 | test |

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)

1 | public int findTargetSumWays(int[] nums, int s) { |

Here is C++ solution (3 ms)

1 | class Solution { |

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

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

C++ iterative with unordered_map

1 | class Solution { |

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.

- O(2^n) brute force

1 | int findTargetSumWays(vector<int>& nums, int S) { |

- 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 | int findTargetSumWays(vector<int>& nums, int S) { |

- O(ns) dp, most dp problems visits continuous states and this is a great example to use hashtable to visit valid states only.

1 | int findTargetSumWays(vector<int>& nums, int S) { |

- O(ns) time, linear space dp.

1 | int findTargetSumWays(vector<int>& nums, int S) { |

- 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.

1 | int findTargetSumWays(vector<int>& nums, int S) { |

#### python

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

Python DP

1 | class Solution(object): |

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.

1 | class Solution(object): |