494. 目標和 - 力扣（LeetCode）

方法一，暴力dfs

直接進行深搜查找出所有的情況，缺點嚴重超時，只能過20個案例

留一下超時的

class Solution {//首先定義全局變量int[] abs = { +1, -1 };   //用來記錄當前遍歷的數的正負List<List<Integer>> list; //所有的結果List<Integer> res;         //記錄當前的結果public int findTargetSumWays(int[] nums, int target) {//初始化res = new LinkedList<>();list = new ArrayList<>();dfs(nums, target, 0, 0);return list.size();}//可直接套用dfs模版public void dfs(int[] nums, int target, int sum, int index) {//如果滿足條件則把當前的記錄加入所有的結果當中if (res.size() == nums.length && sum == target) {list.add(new ArrayList<>(res));return;}//從index進行遍歷，避免遍歷重復數據for (int i = index; i < nums.length; i++) {//遍歷數字的正負兩種情況for (int j = 0; j < 2; j++) {int x = nums[i] * abs[j];res.add(x);dfs(nums, target, sum + x, i + 1);//剪枝，移除最后的數據res.remove(res.size() - 1);}}}
}

dfs優化： 可通過

因為這一道題不需要記錄所有的方法，只需要統計一共的個數，所以可以進行優化

class Solution {//定義全局變量int count = 0;public int findTargetSumWays(int[] nums, int target) {count = 0;dfs(nums, target, 0, 0);return count;}public void dfs(int[] nums, int target, int sum, int index) {if (index == nums.length) {//這里的if不能合并，因為不管sum滿不滿足條件，都需要回溯if (sum == target) {count++;}return;}//當前數為正數dfs(nums, target, sum + nums[index], index + 1);//當前數為負數dfs(nums, target, sum - nums[index], index + 1);}
}