首页 > 编程语言(其他) > 个人记录-LeetCode 77. Combinations

个人记录-LeetCode 77. Combinations

问题:
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],
]

按照我们做排列的思路写代码即可:
1、按顺序从小到达排列n个数。
2、从中取出k个数,其实就是先取出1个 (k种可能),然后从剩下的k-1个中再取出一个(k-1种可能),以此类推。

为了保证取出的组合不重复,我们保证下一个取出的数一定在当前数的后面即可。
即第1个数取了1后,第二个数只能从2~n中取;第1个数取了2后,第二个数只能从3~n中取 (取了2再取1,会和取了1再取2重复)。

整体来讲结果就是将第1位为1的所有排列取完后,才开始取所有第1位为2的排列,依次类推。

代码示例:

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> rst = new ArrayList<>();

        if (n < 0 || k < 0 || n < k) {
            return rst;
        }

        //初始化数组
        int[] nInts = new int[n];
        for (int i = 0; i < n; ++i) {
            nInts[i] = i+1;
        }

        List<Integer> curr = new ArrayList<>();
        for (int i = 0; i <= n-k; ++i) {
            //依次安排好第1位,这个其实是基于深度优先的迭代
            combineInner(rst, nInts, i, curr, k);
        }

        return rst;
    }

    private void combineInner(List<List<Integer>> rst, int[] nInts, int next, List<Integer> curr, int sz) {
        //将当前数加入结果队列
        List<Integer> newList = new ArrayList<>(curr);
        newList.add(nInts[next]);

        //判断长度是否满足了条件
        if (newList.size() == sz) {
            rst.add(newList);
            return;
        }

        //依次加入当前位之后的数
        for (int i = next+1; i <= nInts.length - (sz - newList.size()); ++i) {
            combineInner(rst, nInts, i, newList, sz);
        }
    }
}
作者:Gaugamela 发表于2017/1/9 20:40:43 原文链接
阅读:128 评论:0 查看评论
分类: 编程语言(其他) 标签: