[Leetcode 77] 组合

题目链接:https://leetcode-cn.com/problems/combinations/

递归方法一(剪枝)

剪枝的思路是当tmp_list现有长度和剩余可选元素个数之和小于目标值k时,一定无法得到一个结果。此时直接返回。

时间复杂度:\(O\left(\left(\begin{array}{l}n \\ k\end{array}\right) \times k\right)\)。考察dfs方法执行了多少次,即tmp_list + [i]执行了多少次。总计\(C(n, k)\)个解,每个解需要执行k次。

空间复杂度:\(O(k)\)。栈的深度最多为k层,tmp_list的长度最多为k。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(start, tmp_list, length):
            if length + (n + 1 - start) < k:
                return 
            if length == k:
                res_list.append(tmp_list)
                return
            for i in range(start, n+1):
                dfs(i+1, tmp_list + [i], length+1)
        res_list = []
        dfs(1, [], 0)
        return res_list

递归方法二(数学公式)

排列组合有如下公式。则我们写出一个combine方法,反复调用自身,可得最后的结果。

\(C_{n}^{k} = C_{n-1}^{k} + C_{n-1}^{k-1}\)

时间复杂度:\(O\left(\left(\begin{array}{l}n \\ k\end{array}\right) \times k\right)\)。主要执行的操作是res.append()和k==1时的二维list生成。生成每个解的复杂度为k。因为每个解都是k个元素。总共有\(C(n, k)\)个解。

空间复杂度:\(O(n)\)。栈的深度最多为n层。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]: 
        if n < 1 or k < 1 or k > n:
            return []
        if k == 1:
            return [[i] for i in range(1, n+1)]
        res = self.combine(n-1, k)
        for i in self.combine(n-1, k-1):
            res.append(i + [n])
        return res

注意边界条件,题目给定n和k为整数,则n和k可能为负数或者0。

边界测试用例为n = 0,k = 0, n < k, n = k != 0,n > k,n>=k,k=1,n < 0 or k < 0。

非递归方法

非递归方法不是用栈去模拟递归的方法。这里借鉴itertools.combinations的源码。整体的思路和递归方法一一样,只是使用模拟的方法将结果进行输出。

假设我们n=8,k=5。我们的初始序列是12345,终止序列是45678。我们按照从小到大的顺序来保存所有的结果。

即12345,12346,12347,12348,12356,12357...

我们可以看到当末位增加到8时,次末位加1为5,由于末位始终保持比次末位大,此时更新为次末位加1为6。

将k个数分为前k1个数和后k2个数。k1+k2 = k。当后k2个数无法再增大时,前k1个数的末位加1。后k2个数恢复成此时所能表示的最小值。在这个基础上继续增大。第i位所能表示的最大值位n-k+i+1,i表示索引,从0开始。当所有位均达到了其所能表示的最大值时,此时应该结束模拟的过程。

时间复杂度:\(O\left(\left(\begin{array}{l}n \\ k\end{array}\right) \times k\right)\)。总共有\(C(n, k)\)个解。由上一个解生成下一个解。最多修改k个值。

空间复杂度:\(O(k)\)。nums大小为k。

代码如下:

class Solution:
    def combine(self, n: int, k: int):-> List[List[int]]:
        if k > n:
            return []
        nums = [i for i in range(1, k+1)]
        res = []
        while True:
            res.append(nums.copy())
            for i in reversed(range(k)):
                if nums[i] != n - k + i + 1:
                    break
            else: # for循环正常结束会执行,若break执行了,则跳过
                return res
            nums[i] += 1
            for j in range(i+1, k):
                nums[j] = nums[j-1] + 1
        return res

一般地,如果要求我们对任意iterable对象,输出所有可能的组合。即转化为对其索引进行组合。按照索引输出结果即可。

Python库方法

class Solution:
    def combine(self, n: int, k: int):-> List[List[int]]:
        nums = [i for i in range(1, n+1)]
        return list(itertools.combinations(nums, k))

源码如下:

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

时间复杂度:\(O\left(\left(\begin{array}{l}n \\ k\end{array}\right) \times k\right)\)。总共有\(C(n, k)\)个解。由上一个解生成下一个解。最多修改k个index值。

空间复杂度:\(O(n)\)。pool大小为n,indices大小为k。

上一篇:【Beta Scrum】冲刺!5/5


下一篇:77. C#中的接口和类有什么异同?