# LeetCode-494. Target Sum(DFS&DP)

Datetime:2017-04-11 05:48:12         Topic: LeetCode          Share        Original >>

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

DFS:

public class Solution {
private int cnt = 0;
public int findTargetSumWays(int[] nums, int S) {
if (nums == null)
return 0;
dfs(nums, S, 0, 0);
return cnt;
}

public void dfs(int[] nums, int s, int k, int sum) {
if (k == nums.length) {
if (s == sum)
cnt ++;
return ;
}
dfs(nums, s, k+1, sum+nums[k]);
dfs(nums, s, k+1, sum-nums[k]);
}
}

DP:

public class Solution {
public int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for (int n : nums)
sum += n;
// 两种情况找不到结果，找得到的话就用subsetSum去找，证书和是(s + sum) >>> 1，也就是除以2
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;// 初始记录0的位置为1
for (int n : nums)
// 对每个元素，看看他现有能和别的元素相加得到哪些位置的数
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}
}

http://blog.csdn.net/Cloudox_/article/details/64905139?locationNum=1&fps=1