77. 组合

>> 饿了么、美团外卖红包领取地址<<

题目：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点要求转化成代码即为本题解。