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

组合

• 给定两个整数 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]]}
}

时间空间复杂度

• 时间复杂度：O(C(n, k) * k)，其中 C(n, k) 是从 n 个数中选 k 个数的组合数。生成每个组合需要 O(k) 的时间。
• 空间复杂度：O(k)，递归栈的深度最多为 k，存储当前组合的路径 path 也需要 O(k) 的空间。