回溯python达到的时间限制（合计总和）leetcode poping函数返回后的最后一个元素out

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 

与<-的条目表示的是在测试的组合，这是不必要的，并未经其他程序测试。

此外，由于您生成了额外的候选人，您还需要在每种可能的解决方案上花费额外的时间，以确保它不在解决方案集中（以避免重复）。这是其他解决方案不需要的，因为每个候选人都是唯一的。这个额外的测试也增加了你的运行时间，使它更糟糕。但是，要解决的主要问题是您测试的候选人数量！