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种情况处理。

    a、组合中一定没有n,则k个数需要从剩下的n-1个数中选取,组合结果为C(n-1,k)

    b、组合中一定有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点要求转化成代码即为本题解。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏