# Combinations

Given two integers n and k, return all possible ombinations 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],
]``````

## 回溯法

### 代码

``````public class Solution {

List<List<Integer>> res = new ArrayList<List<Integer>>();

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

private void dfs(int start, int k, int n, List<Integer> tmp){
// 当已经选择足够数字时，将tmp加入结果
if(k == 0){
}
// 每一种选择数字的可能
for(int i = start; i <= n; i++){
dfs(i + 1, k - 1, n, tmp);
tmp.remove(tmp.size() - 1);
}
}
}``````

## 公式法

### 思路

\$\$ C_{n}^{k}=C_{n-1}^{k-1}\cup n+C_{n-1}^{k}\$\$

### 代码

``````public class Solution {
public List<List<Integer>> combine(int n, int k) {
// Recursion: C(n, k) = C(n-1, k-1) U n + C(n-1, k)
// Base: C(0, k) C(n, 0) n < k ---> empty
if(n < k || n == 0 || k == 0){
return res;
}
// C(n-1, k-1) U n
List<List<Integer>> temp = combine(n-1, k-1);
// 加入一个空列表，防止跳过for循环
if(temp.isEmpty()){
}
for(List<Integer> list : temp){