C/C++教程

Leetcode 77 组合

本文主要是介绍Leetcode 77 组合，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在这里插入图片描述
思路

在这里插入图片描述

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        paths = []
        path = []
        def backtrack(n, k, start):
            if len(path) == k:
                paths.append(path[:])

            for i in range(start, n+1):
                path.append(i)
                backtrack(n, k, i+1)
                path.pop()

        backtrack(n, k, 1)
        return paths

优化一下
k-len(path）用来检测还需要多少元素，在1-n中至多要从该起始位 n - (k - len(path) + 1，开始遍历，+1代表左闭集合
距离n=k=4，则第一层为例，i最多取到1，对应结果[1,2,3,4]
在这里插入图片描述

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        paths = []
        path = []
        def backtrack(n, k, start):
            if len(path) == k:
                paths.append(path[:])
                return
            for i in range(start, n-(k-len(path)) + 2):
                path.append(i)
                backtrack(n, k, i+1)
                path.pop()

        backtrack(n, k, 1)
        return paths
这篇关于Leetcode 77 组合的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航