豆包 LeetCode 39. 组合总和 Java实现

题目说明LeetCode39 组合总和给定无重复元素候选数组 candidates 和目标 target 可以重复选取数组元素找出所有和为 target 的组合。同一个数字可以多次选用组合顺序无关不能重复输出组合回溯DFS实现Java完整代码javaimport java.util.ArrayList;import java.util.List;class Solution {public ListList combinationSum(int[] candidates, int target) {ListList res new ArrayList();List path new ArrayList();backtrack(candidates, target, 0, path, res);return res;}/** * param start 只从start往后选避免产生[2,3]和[3,2]重复组合 * param path 当前选中的数字路径 */ private void backtrack(int[] candidates, int remain, int start, ListInteger path, ListListInteger res) { if (remain 0) { res.add(new ArrayList(path)); return; } if (remain 0) { return; } for (int i start; i candidates.length; i) { int val candidates[i]; path.add(val); // 仍从i开始允许重复选取当前元素 backtrack(candidates, remain - val, i, path, res); path.remove(path.size() - 1); // 回溯撤销选择 } }}核心思路回溯DFS逐个枚举候选数字start索引去重只从start向后遍历防止不同排列视为不同答案例如 [2,3] 与 [3,2] 允许重复选取递归下一层起点仍然是 i 而不是 i1递归终止剩余值 remain 0 收集答案 remain0 剪枝返回复杂度简要分析时间指数级 O(2^N)取决于可行组合数量空间O(target)递归栈深度测试示例javapublic static void main(String[] args) {Solution solnew Solution();int[] arr{2,3,6,7};System.out.println(sol.combinationSum(arr,7));//输出 [[2,2,3],[7]]}如果你需要我可以提供剪枝优化版本先排序提前终止循环。