LeetCode 77,组合挑战,你能想出不用递归的解法吗?

738 阅读8分钟

本文始发于个人公众号:TechFlow,原创不易,求个关注


今天是LeetCode第46篇文章,我们一起来LeetCode中的77题,Combinations(组合)。

这个题目可以说是很精辟了,仅仅用一个单词的标题就说清楚了大半题意了。这题官方难度是Medium,它在LeetCode当中评价很高,1364人点赞,只有66个反对。通过率53.6%。

题意

题目的题意很简单,给定两个整数n和k。n表示从1到n的n个自然数,要求随机从这n个数中抽取k个的所有组合

样例

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

全排列的问题我们已经很熟悉了,那么获取组合的问题怎么做呢?

递归

这是一个全组合问题,实际上我们之前做过全排列问题。我们来分析一下排列和组合的区别,可能很多人知道这两者的区别,但是对于区别本身的理解和认识不是非常深刻。

排列和组合有一个巨大的区别在于,排列会考虑物体摆放的顺序。也就是说同样的元素构成,只要这些元素一些交换顺序,那么就会被视为是不同的排列。然而对于组合来说,是不会考虑物体的摆放顺序的。只要是这些元素构成,无论它们怎么调换摆放顺序,都是同一种组合。

我们获取全排列的时候用的是回溯法,我们当然也可以用回溯法来获取组合。但问题是,我们怎么保证获取到的组合都是元素的组成不同,而不是元素之间的顺序不同呢?

为了保证这一点,需要用到一个惯用的小套路,就是通过下标递增来控制拿取元素的顺序。如果我们限定了拿取元素的下标是递增的,那么就可以保证每一次拿取到的组合都是独一无二的。所以我们就把这一点加在回溯法上即可,只要理解了,并不难实现。

在代码的实现当中,我们用上了闭包,省略了几个参数的传递,整体上来说编码的难度降低了一些。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(start, cur):
            # 如果当前已经拿到了K个数的组合,直接加入答案
            # 注意要做深拷贝,否则在之后的回溯过程当中变动也会影响结果
            if len(cur) == k:
                ret.append(cur[:])
                return
            
            # 从start+1的位置开始遍历
            for i in range(start+1, n):
                cur.append(i+1)
                dfs(i, cur)
                # 回溯
                cur.pop()
                
        ret = []
        dfs(-1, [])
        return ret

迭代

这题并不是只有一种做法,我们也可以不用递归实现算法。不用递归意味着没有系统帮助我们建栈存储中间信息了,需要我们自己把迭代过程当中所有变量的关系整理清楚。

我们假设n=8,k=3,那么在所有合法的组合当中,最小的组合一定是[1,2,3],最大的组合一定是[6,7,8]。如果我们保证组合当中的元素是有序排列的,那么组合之间的大小关系也是可以确定的。进而我们可以思考设计一种方案,使得我们可以从最小的组合[1,2,3]一直迭代到[6,7,8],并且我们还要保证在迭代的过程当中,组合当中元素的顺序不会被打乱。

我们可以想象成这n个数在一根“直尺”上排成了一行,我们有k个滑动框在上面移动。这k个滑动框取值的结果就是n个元素中选取k个的组合,并且由于滑动框之间是不能交错的,所以保证了这k个值是有序的。我们要做的就是设计一种移动滑动框的算法,使得能够找到所有的组合情况。

我们可以想象一下,一开始的时候滑动框都聚集在最左边,我们要移动只能移动最右侧的滑动框。我们把滑动框从k移动到了k+1,那么这个时候它的右侧有k-1个滑动框,一共有k个位置。

那么这个问题其实转化成了k个元素当中取k-1个组合的子问题。我们把1-k的这个部分看成是新的“直尺”,我们要在其中移动k-1个滑动框获取所有的组合。首先,我们需要把这k-1个滑动框全部移动到左侧,然后再移动其中最右侧的滑动框。然后循环往复,直到所有的滑动框都往右移动了一格为止,这其实是一个递归的过程。

我们不去深究这个递归的整个过程,我们只需要理解清楚其中的几个关键点就可以了。首先,对于每一次递归来说,我们只会移动这个递归范围内最右侧的滑动框,其次我们清楚每一次递归过程中的起始状态。开始状态就是所有的滑动框全部集中在“直尺”的最左侧,结束状态就是全部集中在最右侧。

我们把上面的逻辑整理一下,假设我们经过一系列操作之后,m个滑动框全部移动到了长度为n的直尺的最右侧。这就相当于的组合都已经获取完了。如果n+1的位置还有滑动框,并且它的右侧还可以移动,那么我们需要将它往右移动一个,到n+2的位置。这个时候剩下的局面就是,为了获取这些组合,我们需要把这m个滑动框全部再移动到直尺的最左侧,重新开始移动。

我们在实现的时候当然没有滑动框,我们可以用一个数组记录滑动框当中的元素。

我先用递归写一下这段逻辑:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def comb(window, m, ret):
            ret.append(window[:-1])

            # 如果第m位的滑动框不超过直尺的范围并且m右侧的滑动框
            while window[m] < min(n - k + m + 1, window[m+1] - 1):
                # 向右滑动一位
                window[m] += 1
                # 如果m左侧还有滑动框,递归
                if m > 0:
                    # 把左侧的滑动框全部移动到最左侧
                    window[:m] = range(1, m+1)
                    comb(window, m-1, ret)
                else:
                    # 否则记录答案
                    ret.append(window[:-1])

                
        ret = []
        window = list(range(1, k+1))
        # 额外多放一个滑动框作为标兵
        window.append(n+1)
        comb(window, k-1, ret)
        return ret

这种解法的速度比上面正规递归的速度快了许多,因为我们递归的过程当中做了诸多限制,剪掉了很多无关的情况,相当于做了极致的剪枝。

最关键的是上面的这段逻辑我们是可以用循环实现的,所以我们可以用循环来将递归的逻辑展开,就得到了下面这段代码。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 构造滑动框
        window = list(range(1, k + 1)) + [n + 1]
        
        ret, j = [], 0

        while j < k:
            # 添加答案
            ret.append(window[:k])

            j = 0
            # 从最左侧的滑动框开始判断
            # 如果滑动框与它右侧滑动框挨着,那么就将它移动到最左侧
            # 因为它右侧的滑动框一定会向右移动
            while j < k and window[j + 1] == window[j] + 1:
                window[j] = j + 1
                j += 1
            # 连续挨着最右侧的滑动框向右移动一格
            window[j] += 1
            
        return ret

这段代码虽然非常精炼,但是很难理解,尤其是你没能理解上面递归实现的话,会更难理解。所以我建议,先把递归实现的滑动框的方法理解了,再来理解不含递归的这段,会容易一些。

总结

我们通过回溯法求解组合的方法应该是最简单也是最基础的,难度也不大。相比之下后面一种方法则要困难许多,我们直接去啃,往往不得要领。既会疑惑为什么这样可以保证能获得所有的组合,又会不明白其中具体的实现逻辑。所以如果想要弄明白第二种方法,一定要从滑动框这个模型出发

从代码实现的角度来说,滑动框方法的递归解法比非递归的解法还要困难。因为递归条件以及逻辑都比较复杂,还涉及到存储答案的问题。但是从理解上来说,递归的解法更加容易理解一些,非递归的算法往往会疑惑于j这个指针的取值。所以如果想要理解算法的话,可以从递归的代码入手,想要实现代码的话,可以从非递归的方法入手。

这道题目非常有意思,值得大家细细思考。

如果喜欢本文,可以的话,请点个关注,给我一点鼓励,也方便获取更多文章。

本文使用 mdnice 排版