494. Target Sum

  • 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
2
3
4
5
6
7
8
9
10
11
12
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

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

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int cnt = 0;
dfs(nums, 0, nums.size(), 0, S, cnt);
return cnt;
}

void dfs(vector<int>& nums, int k, int n, int target, int& S, int& cnt){
if(k==n){
if(target==S)
cnt++;
return;
}
dfs(nums, k+1, n, target+nums[k], S, cnt);
dfs(nums, k+1, n, target-nums[k], S, cnt);
}
};

方法二:

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

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = accumulate(nums.begin(), nums.end(), 0);
// sum < S 这种情况要考虑到
return (sum+S)&1 || sum < S ? 0 : helper(nums, (sum+S)>>1);
}

int helper(vector<int>& nums, int target){
vector<int> dp(target+1, 0);
dp[0] = 1;
// 之所以这样遍历,可以参考416位运算,就是移位相加
// 从后向前遍历保证了不会出错
for(auto num:nums)
for(int i=target; i>=num; i--)
dp[i] += dp[i-num];
return dp[target];
}
};

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:

1
2
3
4
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

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for (int n : nums)
sum += n;
return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1);
}

public int subsetSum(int[] nums, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}

Here is C++ solution (3 ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int s) {
int sum = accumulate(nums.begin(), nums.end(), 0);
return sum < s || (s + sum) & 1 ? 0 : subsetSum(nums, (s + sum) >> 1);
}

int subsetSum(vector<int>& nums, int s) {
int dp[s + 1] = { 0 };
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}
};

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


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

C++ iterative with unordered_map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
unordered_map<int, int> ans;
ans[0] = 1;
for (int n : nums) {
unordered_map<int, int> newAns;
for (auto p : ans) {
int sum = p.first, cnt = p.second;
newAns[sum + n] += cnt;
newAns[sum - n] += cnt;
}
ans = newAns;
}
return ans[S];
}
};

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
2
3
4
5
6
7
int findTargetSumWays(vector<int>& nums, int S) {
return find(0,nums,S);
}
int find(int p, vector<int>& nums, int sum) {
if(p==nums.size()) return sum==0;
return find(p+1,nums,sum+nums[p])+find(p+1,nums,sum-nums[p]);
}
  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
2
3
4
5
6
7
8
9
10
int findTargetSumWays(vector<int>& nums, int S) {
vector<unordered_map<int,int>> mem(nums.size());
return find(0,nums,S,mem);
}
int find(int p, vector<int>& nums, int sum, vector<unordered_map<int,int>>& mem) {
if(p==nums.size()) return sum==0;
auto it = mem[p].find(sum);
if(it != mem[p].end()) return it->second;
return mem[p][sum]=find(p+1,nums,sum+nums[p],mem)+find(p+1,nums,sum-nums[p],mem);
}
  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
2
3
4
5
6
7
8
9
10
11
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size();
vector<unordered_map<int,int>> dp(n+1);
dp[0][0]=1;
for(int i=0;i<n;i++)
for(auto &p:dp[i]) {
dp[i+1][p.first+nums[i]] += p.second;
dp[i+1][p.first-nums[i]] += p.second;
}
return dp[n][S];
}
  1. O(ns) time, linear space dp.
1
2
3
4
5
6
7
8
9
10
11
12
int findTargetSumWays(vector<int>& nums, int S) {
unordered_map<int,int> cur({{0,1}}), nxt, *p_cur=&cur, *p_nxt=&nxt;
for(int i=0;i<nums.size();i++) {
for(auto &p:*p_cur) {
(*p_nxt)[p.first+nums[i]] += p.second;
(*p_nxt)[p.first-nums[i]] += p.second;
}
swap(p_cur,p_nxt);
p_nxt->clear();
}
return (*p_cur)[S];
}
  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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findTargetSumWays(vector<int>& nums, int S) {
int sum = accumulate(nums.begin(),nums.end(),0);
if(S>sum || S<-sum) return 0;
vector<int> cur(2*sum+1), nxt(2*sum+1), *p_cur = &cur, *p_nxt = &nxt;
cur[sum] = 1;
for(int i=0;i<nums.size();i++) {
for(int j=0;j<=2*sum;j++)
if(p_cur->at(j)) {
p_nxt->at(j+nums[i]) += p_cur->at(j);
p_nxt->at(j-nums[i]) += p_cur->at(j);
}
swap(p_cur,p_nxt);
p_nxt->assign(2*sum+1,0);
}
return p_cur->at(S+sum);
}

python


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

Python DP

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def findTargetSumWays(self, nums, S):
if not nums:
return 0
dic = {nums[0]: 1, -nums[0]: 1} if nums[0] != 0 else {0: 2}
for i in range(1, len(nums)):
tdic = {}
for d in dic:
tdic[d + nums[i]] = tdic.get(d + nums[i], 0) + dic.get(d, 0)
tdic[d - nums[i]] = tdic.get(d - nums[i], 0) + dic.get(d, 0)
dic = tdic
return dic.get(S, 0)

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
def findTarget(i, s):
if (i, s) not in cache:
r = 0
if i == len(nums):
if s == 0:
r = 1
else:
r = findTarget(i+1, s-nums[i]) + findTarget(i+1, s+nums[i])
cache[(i, s)] = r
return cache[(i, s)]

cache = {}
return findTarget(0, S)
谢谢你,可爱的朋友。