77.组合

题目:77.组合

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

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

• 示例 1：

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

• 示例 2：

输入：n = 1, k = 1
输出：[[1]]

• 提示：

1 <= n <= 20
1 <= k <= n

思路

可以通过回溯算法来解决。从 [1, n] 中选择 k 个数，并返回所有可能的组合。

解决思路

1. 递归选择数字：每次从当前数字 begin 开始，选择下一个数字，递归地继续选择直到选择了 k 个数字。
2. 终止条件：当当前组合的长度等于 k 时，将该组合加入结果列表。
3. 回溯：递归返回时撤销上一步选择，继续选择其他可能的数字。

• 时间复杂度:O(C(n, k) * k)，其中 n 是元素个数，k 是每个组合的长度。
• 空间复杂度:O(C(n, k) * k)，其中 n 是元素个数，k 是每个组合的长度。

代码

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new LinkedList<>();
    // 从1开始构建组合
    dfs(result, n, k, 1, new LinkedList<>());
    return result;
}

// 回溯方法
private void dfs(List<List<Integer>> result, int n, int k, int begin, LinkedList<Integer> current) {
    // 如果当前组合的长度等于k，将其加入结果列表
    if (current.size() == k) {
        result.add(new ArrayList<>(current));
        return;
    }
    // 从start开始选择数，直到n
    for (int i = begin; i <= n; i++) {
        // 选择当前数i
        current.add(i);
        // 递归选择下一个数，从i+1开始，继续构建组合
        dfs(result, n, k, i + 1, current);
        // 回溯，撤销上一步选择
        current.removeLast();
    }
}