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

思路

与全排列的算法比较像，不同的是此处求组合，需要用一个start变量控制当前搜索到的分支，即只搜索start之后的区间，避免跟之前的结果重复。

class Solution {

    int n, k;
    List<List<Integer>> ans;


    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        ans = new ArrayList<>();
        dfs(new ArrayList<>(), 1);
        return ans;
    }


    public void dfs(List<Integer> list, int start) {
        if (list.size() == k) {
            ans.add(new ArrayList<>(list));
            return;
        }
        // i从start开始，不往回走
        for (int i = start; i <= n; i++) {
            list.add(i);
            dfs(list, i + 1);
            list.remove(list.size() - 1);
        }


    }
}

复杂度

  • 时间复杂度：。
  • 空间复杂度：。