【問題描述】[中等]

【解答思路】

1. 回溯

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List;public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {int len = candidates.length;List<List<Integer>> res = new ArrayList<>();if (len == 0) {return res;}Deque<Integer> path = new ArrayDeque<>();dfs(candidates, 0, len, target, path, res);return res;}/*** @param candidates 候選數組* @param begin 搜索起點* @param len 冗余變量，是 candidates 里的屬性，可以不傳* @param target 每減去一個元素，目標值變小* @param path 從根結點到葉子結點的路徑，是一個棧* @param res 結果集列表*/private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {// target 為負數和 0 的時候不再產生新的孩子結點if (target < 0) {return;}if (target == 0) {res.add(new ArrayList<>(path));return;}// 重點理解這里從 begin 開始搜索的語意for (int i = begin; i < len; i++) {path.addLast(candidates[i]);// 注意：由于每一個元素可以重復使用，下一輪搜索的起點依然是 i，這里非常容易弄錯dfs(candidates, i, len, target - candidates[i], path, res);// 狀態重置path.removeLast();}} }作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

正向思維 求和（增加了空間和變量）

class Solution {public List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {dfs(candidates,target,new ArrayDeque<Integer>(),0,0);return res;}public void dfs(int[] cand,int target,Deque<Integer> temp,int sum,int index){if(sum>target) return;if(sum==target){res.add(new ArrayList<>(temp));return;}for(int i=index;i<cand.length;++i){temp.addLast(cand[i]);dfs(cand,target,temp,sum+cand[i],i);temp.removeLast();}} }

2. 回溯剪樹枝

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; import java.util.List;public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {int len = candidates.length;List<List<Integer>> res = new ArrayList<>();if (len == 0) {return res;}// 排序是剪枝的前提Arrays.sort(candidates);Deque<Integer> path = new ArrayDeque<>();dfs(candidates, 0, len, target, path, res);return res;}private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {// 由于進入更深層的時候，小于 0 的部分被剪枝，因此遞歸終止條件值只判斷等于 0 的情況if (target == 0) {res.add(new ArrayList<>(path));return;}for (int i = begin; i < len; i++) {// 重點理解這里剪枝，前提是候選數組已經有序，if (target - candidates[i] < 0) {break;}path.addLast(candidates[i]);dfs(candidates, i, len, target - candidates[i], path, res);path.removeLast();}} }作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/

【總結】

1. 總結

2.在函數中調用dfs時，直接初始化變量，不用另外創建新的變量

3.回溯算法相關題目

[Leedcode][JAVA][第46題][全排列][回溯算法]
[Leetcode][第81題][JAVA][N皇后問題][回溯算法]
[Leetcode][第60題][JAVA][第k個排列][回溯][DFS][剪枝]

轉載鏈接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/

總結

以上是生活随笔為你收集整理的[Leetcode][第39题][JAVA][组合总和][回溯][dfs][剪枝]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。