Leetcode之深度优先搜索（DFS）专题-494. 目标和（Target Sum）
深度优先搜索的解题详细介绍，点击
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 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 一共有5种方法让最终目标和为3。
分析：
要求给数组每个数字加+或者-，使最后的表达式的值为S。
那我们可以换个思路想，把这些全部先加起来，我们只需要加减号就可以了。
例如图中的例子 sum=5，那如果我要添加一个减号的话，sum需要减2倍的nums[i] DFS解决，加减号或者不加减号。
class Solution {
int ans = 0;
public int findTargetSumWays(int[] nums, int S) {
if (nums.length == 0)
return 0;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
Arrays.sort(nums);
dfs(nums, nums.length - 1, S, sum);
return ans;
}
public void dfs(int[] nums, int step, int S, int sum) {
if (step < 0) {
if (sum == S) {
ans++;
}
return;
}
if (sum < S) {
return;
}
dfs(nums, step - 1, S, sum - (2 * nums[step]));
dfs(nums, step - 1, S, sum);
}
}