当前位置：首页 > news >正文

058组合总和

news 2026/5/25 15:09:00

组合总和

题目链接：https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> 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, List<Integer> output, List<List<Integer>> ans){ if(sum == target){ ans.add(new ArrayList<>(output)); return; } if(sum > target){ return; } int length = candidates.length; for(int i=startIndex; i<length; 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 List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> ans = new ArrayList<List<Integer>>(); List<Integer> combine = new ArrayList<Integer>(); dfs(candidates, target, ans, combine, 0); return ans; } public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) { if (idx == candidates.length) { return; } if (target == 0) { ans.add(new ArrayList<Integer>(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 List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> ans = new ArrayList<>(); dfs(candidates, target, 0, new ArrayList<>(), ans); return ans; } //startIndex：每次选取的初始位置（我们只需让下一次选取从上一次选取的位置开始，就可避免出现重复组合，同时进行剪枝） public void dfs(int[] candidates, int target, int startIndex, List<Integer> output, List<List<Integer>> ans){ if(target == 0){ ans.add(new ArrayList<>(output)); return; } int length = candidates.length; for(int i=startIndex; i<length; 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则直接跳过这个数。