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

题目说明

LeetCode39 组合总和
给定无重复元素候选数组 candidates 和目标 target ，可以重复选取数组元素，找出所有和为 target 的组合。

• 同一个数字可以多次选用
• 组合顺序无关，不能重复输出组合
• 回溯DFS实现

Java完整代码

java

import java.util.ArrayList;
import java.util.List;

class Solution {
public List<List> combinationSum(int[] candidates, int target) {
List<List> 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, List<Integer> path, List<List<Integer>> 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); // 回溯撤销选择 } }

}

核心思路

1. 回溯+DFS：逐个枚举候选数字
2. start索引去重：只从start向后遍历，防止不同排列视为不同答案（例如 [2,3] 与 [3,2] ）
3. 允许重复选取：递归下一层起点仍然是 i 而不是 i+1
4. 递归终止：剩余值 remain == 0 收集答案； remain<0 剪枝返回

复杂度简要分析

• 时间：指数级 O(2^N)，取决于可行组合数量
• 空间：O(target)，递归栈深度

测试示例

java

public static void main(String[] args) {
Solution sol=new Solution();
int[] arr={2,3,6,7};
System.out.println(sol.combinationSum(arr,7));
//输出 [[2,2,3],[7]]
}

如果你需要，我可以提供剪枝优化版本（先排序提前终止循环）。