回溯 python 达到时间限制（组合总和）leetcode 在函数 return 之后弹出最后一个元素

Question

我的问题与这个问题https://leetcode.com/problems/combination-sum-iii/discuss/和所有回溯问题有关。

我的问题是：为什么我的代码（真的和其他人的答案很相似）总是比他们的运行时间长？

def combinationSum3(self, k, n):
    """
    :type k: int   how many number
    :type n: int   how much add to
    :rtype: List[List[int]]
    """
    res=[]
    self.backtrack(k, n, [], res)
    newres=[]
    for each in res:
        newres.append(list(each))
    return newres

def backtrack(self, k, n, path, res):
    if len(path)> k or sum(path)>n:
        return 
    if len(set(path))==k and sum(path)==n:
        if set(path) not in res:
            res.append(set(path))
        return

    for i in range(1, 10):
        self.backtrack(k, n, path+[i], res)

其他人过时代码：

# @param {integer} k
# @param {integer} n
# @return {integer[][]}
def combinationSum3(self, k, n):
    if n > sum([i for i in range(1, 11)]):
        return []

    res = []
    self.sum_help(k, n, 1, [], res)
    return res


def sum_help(self, k, n, curr, arr, res):
    if len(arr) == k:
        if sum(arr) == n:
            res.append(list(arr))
        return

    if len(arr) > k or curr > 9:
        return

    for i in range(curr, 10):
        arr.append(i)
        self.sum_help(k, n, i + 1, arr, res)
        arr.pop()

Answer 1

主要区别和变慢是由于您的代码测试的组合比其他解决方案多得多。您生成了所有数字组合，这导致您多次测试 "same" 组合，而另一个解决方案仅生成每个可能的候选对象一次，只允许序列中的下一个数字等于或大于前一个数字.

查看以下有限的候选人列表，其中数字范围限制在 1 到 3 之间：

带有 <- 的条目表示您测试的组合，这些组合是不必要的，并且未被其他程序测试。

此外，由于产生了额外的候选项，您还需要在每个可能的解决方案上花费额外的时间，以确保它不在解决方案集中（避免重复）。其他解决方案不需要这样做，因为每个候选者都是独一无二的。这个额外的测试也会增加你的运行时间，使情况变得更糟。但是，主要要解决的是你测试的考生数量！

回溯 python 达到时间限制（组合总和）leetcode 在函数 return 之后弹出最后一个元素

backtracking python time limit reached (combination sum) leetcode poping last element out after function return

python

permutation

backtracking

depth-first-search