### 题目

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example, If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]


### 回溯算法 $O(n^k)$

#### 代码

public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
backtracking(res,temp,k,1,n+1);
return res;
}
// [from,to):  from=inclusive,  to=exclusive
public void backtracking(List<List<Integer>> res, List<Integer> temp, int remain, int from, int to) {
if (remain == 0) { res.add(new ArrayList<Integer>(temp)); return; }
for (int i = from; i < to; i++) {
backtracking(res,temp,remain-1,i+1,to);
temp.remove(temp.size()-1);
}
}
}


### 基于排列组合公式的递归法

C(n,k) = C(n-1, k-1) U n + C(n-1,k)

#### 代码

public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (k == n) {
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++) { list.add(i); }
return res;
}
if (k == 1) {
for (int i = 1; i <= n; i++) {
List<Integer> temp = new ArrayList<>();
}
return res;
}
res = combine(n-1,k-1);
for (List<Integer> list : res) { list.add(n); }
return res;
}
}


#### 简洁版代码

public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (k > n) { return res; }
if (k == 0) {
return res;
}
res = combine(n-1,k-1);
for (List<Integer> list : res) { list.add(n); }
return res;
}
}


### 动态规划

public class Solution {
public List<List<Integer>> combine(int n, int k) {
Map<String,List<List<Integer>>> memo = new HashMap<>();
return dp(n,k,memo);
}
public List<List<Integer>> dp(int n, int k, Map<String,List<List<Integer>>> memo) {
String key = "" + n + k;
if (memo.containsKey(key)) { return memo.get(key); }
List<List<Integer>> res = new ArrayList<>();
if (k > n) {
memo.put(key,res);
return res;
}
if (k == 0) {
memo.put(key,res);
return res;
}
res = combine(n-1,k-1);
for (List<Integer> list : res) { list.add(n); }