LeetCode-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

题解

笑死，5.04%，但终究通过了不是，问题出在int[]转list上，这里我用的方法很慢，如果path用别的方式储存或许可以加快速度，这里不多赘述了，重点是掌握回溯的方法。

这题和17题还是比较类似的，代码我都用的差不多的代码。

path是每次遍历暂存的结果，这一题path的长度还是固定为k的，关键在于DFS方法，这里传入参数i, j, n, k，i是开始的位置，这里因为没有映射关系，所以用j表示遍历的数字，n和k都是判断的时候用到的。

如果i位置等于k了，说明当前遍历了k个数，需要把path加入到res里了，这里用的方法是Arrays.stream(path).boxed().collect(Collectors.toList())；

不然的话，j <= k的时候，我们继续往后遍历即可i + 1，j + 1。

class Solution {

    private final List<List<Integer>> res = new ArrayList<>();
    private int[] path;

    public List<List<Integer>> combine(int n, int k) {
        // 1 - n 所有可能的k个数的组合
        path = new int[k];
        dfs(0, 1, k, n);
        return res;
    }

    public void dfs(int i, int j, int k, int n) {
        if (i == k) {
            res.add(Arrays.stream(path).boxed().collect(Collectors.toList()));
            return;
        }
        for (; j <= n; j++) {
            path[i] = j;
            dfs(i + 1, j + 1, k, n);
        }
    }
}