手记

77. 组合 - 力扣(Leetcode)

Problem: 77. 组合

思路

1、k=2,用两层for循环,那么k=50呢?50层for循环? 2、因此,本题无法暴力解决,只能用递归栈代替k层for循环。 3、求(n,k)的所有组合问题只能暴力解法,回溯仅仅是让暴力解法落实到编程上。

解题方法

0、按照回溯通用方法,分为三步:

1、确定回溯的返回值和参数(是否需要全局变量)

本题可以在函数的参数中记录结果,但是设置全局变量可以精简代码。

// result存储从根节点递归到叶子节点的一个组合数
// 例如:n=5,k=3,则result的一个结果为[1,2,3]
private List<List<Integer>> result;

// 每一次从根节点递归到叶子节点,path就构成了一个组合数
private List<Integer> path;

通过设定了result和path全局变量,则回溯函数的返回值可以简化为void

设定参数,以及额外的参数:startIndex

由于题目已经给出了两个参数n和k,因此回溯函数的参数肯定是包括这两项的。 我们是否还需要其他参数呢?

这一部分的内容将放在3.回溯的单层逻辑里面讲。

2、确定回溯函数的终止条件

当path中的内容满足题目的条件,即构成一个长度为k的组合数时,需要将path加入到result中。此时,属于是一个路径的结束。

if (path.size() == k) {
    // 因为java中List是引用形式的,因此要做一次拷贝
    List<Integer> clone = new ArrayList<>();
    clone.addAll(path);
    // 添加到结果中
    result.add(clone);
    return;
}

3、确定递归函数的单层逻辑

首先,我将给出单层逻辑,但是其中有两个变量的值,我不确定。

for (int i = ❓; i <= n; i++) {
    path.add(i);
    backTracking(n, k, ❓);
    path.remove(path.size() - 1);
}

单层逻辑并不难写出来,但是每一次递归中,for循环应该从哪一位数开始呢? 我们先看看递归的栈。

因此,在1.确定回溯的返回值和参数中,还需要添加一个参数startIndex,用来控制每一层递归中for循环应该从哪开始。 所以,两个❓,大家应该都知道如何填写了。

复杂度

  • 时间复杂度: O((nk)∗k)O(\tbinom{n}{k}*k)

  • 空间复杂度: O(n+k)O(n+k)(递归使用栈空间的空间代价和临时数组temptemp的空间代价。)

Code


class Solution {
/**
     * 记录结果
     */
    private List<List<Integer>> result;

    /**
     * 符合条件单一结果<br>
     *
     * path这个数组的大小如果达到k,说明我们找到了一个子集大小为k的组合了,也说明到达叶子节点了<br>
     * 此时用result二维数组,把path保存起来,并终止本层递归
     */
    private List<Integer> path;

    /**
     * 1、递归函数的返回值以及参数<br>
     * 在这里要定义两个全局变量,一个用来存放符合条件单一结果,一个用来存放符合条件结果的集合。<br>
     *
     * 2、递归的终止条件
     * 3、单层搜索的过程
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        result = new ArrayList<>();
        path = new ArrayList<>();
        backTracking(n, k, 1);
        return result;
    }

    /**
     * startIndex来记录下一层递归,搜索的起始位置
     * @param n
     * @param k
     * @param startIndex
     */
    public void backTracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            List<Integer> clone = new ArrayList<>();
            clone.addAll(path);
            result.add(clone);
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            // 递归
            backTracking(n, k, i + 1);
            // 回溯
            path.remove(path.size() - 1);
        }
    }
}
0人推荐
随时随地看视频
慕课网APP