题目描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

样例

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

算法1

枚举每个位置选哪些数，记录start表示从start数开始枚举到n，在u的位置放哪些数，递归到下一层

时间复杂度 $O(C_{n}^{k})$

组合类型，直接把答案选出来，从n个数中选k个

Java 代码

class Solution {
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    static List<Integer> t = new ArrayList<Integer>();
    static void dfs(int n,int k,int u,int start)
    {
        if(u == k)
        {
            ans.add(new ArrayList<Integer>(t));
            return ;
        }
        for(int i = start;i <= n;i ++)
        {
            t.add(i);
            dfs(n,k,u + 1,i + 1);
            t.remove(t.size() - 1);
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        ans.clear();
        dfs(n,k,0,1);

        return ans;
    }
}

算法2

枚举每个数 选 还是 不选，并递归到下一层

时间复杂度 （比算法1慢）

$O(2^n)$加部分剪枝

Java 代码

class Solution {
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    static List<Integer> t = new ArrayList<Integer>();
    static void dfs(int n,int k,int u)
    {
        if(t.size() > k) return ;

        if(u == n + 1)
        {
            if(t.size() == k) ans.add(new ArrayList<Integer>(t));
            return ;
        }

        //放
        t.add(u);
        dfs(n,k,u + 1);
        t.remove(t.size() - 1);
        //不放
        dfs(n,k,u + 1);
    }
    public List<List<Integer>> combine(int n, int k) {
        ans.clear();
        dfs(n,k,1);

        return ans;
    }
}