题目：https://leetcode-cn.com/problems/combinations/
代码：
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (k > n || k <= 0) {
//不合法的情况，组合为空
return res;
}
if (k == 1) {
//k为1，则每个数字都是1个组合，共n个组合
for (int i = 1; i <= n; i++) {
List<Integer> c = new ArrayList<>();
c.add(i);
res.add(c);
}
} else if (k == n) {
//k==n，则所有数字是1个组合，共1个组合
List<Integer> c = new ArrayList<>();
for (int i = 1; i <= n; i++) {
c.add(i);
}
res.add(c);
}else{
//k<n，则分2种情况
//1、组合中没n，则剩下n-1个数中需要选k个数
res = this.combine(n - 1, k);
//2、组合中必有n，则剩下n-1个数中需要选k-1个数
List<List<Integer>> cList = this.combine(n - 1, k - 1);
for (List<Integer> c : cList) {
c.add(n);
}
res.addAll(cList);
}
return res;
}
}
题目要求从n个数中选出k个数的所有组合，我们可以分情况来获取。
1、诸如k<=0或者k>n这种不合法的情况直接返回空结果。
2、k=1的情况，那就是每一个数字都是1个组合，直接遍历1-n，每一个数做一个组合返回。
3、k=n的情况，那就是从n个数选n个数，即所有的数一起是一个组合，遍历1-n，所有的数做一个组合返回。
4、k<n的情况，这个是常规的操作，我们可以考虑使用递归，分2种情况处理。
- 组合中一定没有n，则k个数需要从剩下的n-1个数中选取，组合结果为
C(n-1,k) - 组合中一定有n，则还剩k-1个数需要从剩下的n-1个数中选取，组合结果为
C(n-1,k-1)
所以4这种情况下的组合结果最终为：C(n,k)=C(n-1,k)+C(n-1,k-1)。这里的C就是我们的递归函数combine，将上述1到4点要求转化成代码即为本题解。
