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

【回溯】Leetcode 77. 组合【中等】

news 2025/8/7 0:43:15

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

示例 1：

输入： n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

解题思路

定义递归函数：定义一个递归函数 backtrack 用来生成组合。
递归终止条件：如果当前组合的长度达到 k，将其添加到结果列表中。
选择元素：从当前起始元素到 n 进行迭代，选择每个元素加入当前组合。
递归调用：选择元素后，递归调用函数生成下一个元素的组合。
回溯：在递归完成后，移除当前选择的元素，尝试选择下一个元素。

Java实现

public class Combine {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<>();backtrack(1, n, k, new ArrayList<>(), res);return res;}private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> res) {// 如果组合完成if (path.size() == k) {res.add(new ArrayList<>(path));return;}// 从`start`到`n`遍历所有的数字for (int i = start; i <= n; i++) {// 将`i`添加到当前组合path.add(i);// 使用下一个整数完成组合backtrack(i + 1, n, k, path, res);// 回溯，通过移除`i`path.remove(path.size() - 1);}}// 测试用例public static void main(String[] args) {Combine solution = new Combine();System.out.println(solution.combine(4, 2)); // 期望输出: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]System.out.println(solution.combine(5, 3)); // 期望输出: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]}
}