058组合总和

组合总和题目链接https://leetcode.cn/problems/combination-sum/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger ans new ArrayList(); dfs(candidates, target, 0, 0, new ArrayList(), ans); return ans; } //startIndex每次选取的初始位置我们只需让下一次选取从上一次选取的位置开始就可避免出现重复组合 public void dfs(int[] candidates, int target, int sum, int startIndex, ListInteger output, ListListInteger ans){ if(sum target){ ans.add(new ArrayList(output)); return; } if(sum target){ return; } int length candidates.length; for(int istartIndex; ilength; i){ sum candidates[i]; output.add(candidates[i]); dfs(candidates, target, sum, i, output, ans); sum - candidates[i]; output.remove(output.size()-1); } }分析​ 代码的时间复杂度为O(S)其中 S 为所有可行解的长度之和。空间复杂度为O(target)除答案数组外空间复杂度取决于递归的栈深度在最差情况下需要递归 O(target) 层。本题复杂度我不知道该如何表示直接看了官方的​ 解题思路采用基本的递归 回溯方法唯一的难点在于如何避免出现重复组合经过思考我发现由于candidates是一个无重复元素的整数数组所以只需让下一次选取从上一次选取的位置开始就可以避免出现重复组合。看了官方题解后的解答//方法搜索回溯官方版 //时间复杂度O(S)其中 S 为所有可行解的长度之和。 //空间复杂度O(target)除答案数组外空间复杂度取决于递归的栈深度在最差情况下需要递归 O(target) 层。 public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger ans new ArrayListListInteger(); ListInteger combine new ArrayListInteger(); dfs(candidates, target, ans, combine, 0); return ans; } public void dfs(int[] candidates, int target, ListListInteger ans, ListInteger combine, int idx) { if (idx candidates.length) { return; } if (target 0) { ans.add(new ArrayListInteger(combine)); return; } // 直接跳过 dfs(candidates, target, ans, combine, idx 1); // 选择当前数 if (target - candidates[idx] 0) { combine.add(candidates[idx]); dfs(candidates, target - candidates[idx], ans, combine, idx); combine.remove(combine.size() - 1); } } //方法搜索回溯看了官方解答后对我的解答进行优化版 //时间复杂度O(S)其中 S 为所有可行解的长度之和。 //空间复杂度O(target)除答案数组外空间复杂度取决于递归的栈深度在最差情况下需要递归 O(target) 层。 public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger ans new ArrayList(); dfs(candidates, target, 0, new ArrayList(), ans); return ans; } //startIndex每次选取的初始位置我们只需让下一次选取从上一次选取的位置开始就可避免出现重复组合同时进行剪枝 public void dfs(int[] candidates, int target, int startIndex, ListInteger output, ListListInteger ans){ if(target 0){ ans.add(new ArrayList(output)); return; } int length candidates.length; for(int istartIndex; ilength; i){ if(target - candidates[i] 0){ target - candidates[i]; output.add(candidates[i]); dfs(candidates, target, i, output, ans); target candidates[i]; output.remove(output.size()-1); } } }分析官方的解题思路与我的解答基本一致但是在剪枝上进行了优化优化的点在于每次判断target减去当前选取的数后是否小于0若小于0则直接跳过这个数。总结本题采用基本的递归 回溯方法思路简单唯一需要思考的是如何进一步进行剪枝优化。