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

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

主要的区别和减速是由于您的代码比其他解决方案测试更多的组合。生成所有数字的组合，这会导致多次测试“相同”的组合，而另一种解决方案只生成一次每个可能的候选数字，只允许序列中的下一个数字等于或大于上一个数字。你知道吗

请看以下有限的候选名单，其中数字范围限制在1到3之间：

1 1 1
1 1 2
1 1 3
1 2 1 <-
1 2 2
1 2 3
1 3 1 <-
1 3 2 <-
1 3 3
2 1 1 <-
2 1 2 <-
2 1 3 <-
2 2 1 <-
2 2 2
2 2 3
2 3 1 <-
2 3 2 <-
2 3 3
3 1 1 <-
3 1 2 <-
3 1 3 <-
3 2 1 <-
3 2 2 <-
3 2 3 <-
3 3 1 <-
3 3 2 <-
3 3 3

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

此外，由于生成了额外的候选项，您还需要在每个可能的解决方案上花费额外的时间，以确保它不在解决方案集中（以避免重复）。另一个解决方案不需要这样做，因为每个候选方案都是唯一的。这个额外的测试还增加了运行时间，使情况更糟。不过，要解决的主要问题是你考试的考生人数！你知道吗