題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/target-sum
給定一個(gè)非負(fù)整數(shù)數(shù)組岛马，a1, a2, ..., an, 和一個(gè)目標(biāo)數(shù)，S”赴＃現(xiàn)在你有兩個(gè)符號(hào) + 和 -。對(duì)于數(shù)組中的任意一個(gè)整數(shù)怎燥，你都可以從 + 或 -中選擇一個(gè)符號(hào)添加在前面荠锭。
返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號(hào)的方法數(shù)呼股。
示例 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種方法讓最終目標(biāo)和為3耕魄。
注意:
- 數(shù)組非空，且長度不會(huì)超過20彭谁。
- 初始的數(shù)組的和不會(huì)超過1000吸奴。
- 保證返回的最終結(jié)果能被32位整數(shù)存下。
深度優(yōu)先解法：
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int[] ans = {0};
dfs(nums,0,S,ans);
return ans[0];
}
private void dfs(int[] nums,int index,int target,int[] ans){
if(index >= nums.length){
if(target == 0){
ans[0] += 1;
}
return;
}
dfs(nums,index+1,target+nums[index],ans);
dfs(nums,index+1,target-nums[index],ans);
}
}
