Osheep

时光不回头,当下最重要。

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],
]
题意:给出数字n和k,返回从1到n中k个数字的组合。

思路:深度优先搜索,从1开始选,逐个选下一个,选到的数组集合满足k个以后将这个集合加到结果集中,然后把这个结果集中最后一个数字删掉,回溯的加下一个数字。比如n是4,k是3的情况,选出123后;删掉3,加入3的下一个数字4,得到124。

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();
    if (n <= 0 || k > n) {
        return res;
    }

    dfs(n, k, 1, new ArrayList<>(), res);

    return res;
}

private void dfs(int n, int k, int start, List<Integer> subres, List<List<Integer>> res) {
    if (subres.size() == k) {
        res.add(new ArrayList<>(subres));
        return;
    }

//        for (int i = start; i <= n - k + 1; i++) {
    for (int i = start; i <= n; i++) {
//            subres.add(start);
//            dfs(n, k, start + 1, subres, res);
        subres.add(i);
        dfs(n, k, i + 1, subres, res);
        subres.remove(subres.size() - 1);
    }
}

bug:1、循环内处理subres.add和dfs时传入的是start参数;2、想到如果4个数选3个数的情况,如果第一个数字选到了3,那么是没有符合条件的组合的,所以循环终止条件写成了i<=n-k+1,但是没有考虑到选后面几个数字也会调用到这里。

点赞