バックトラッキング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回だけ生成します。

番号の範囲は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 

<-を持つエントリが不要なあなたは、テストの組み合わせを表し、および他のプログラムではテストされません。

また、余分な候補が生成された結果、可能なソリューションごとに余分な時間を費やして、ソリューションセットにまだ存在しないことを確認する必要があります（重複を避けるため）。それは、それぞれの候補が一意であるため、他の解決策では必要ではありません。この余分なテストは実行時間をさらに悪化させます。しかし、修正する主なものは、あなたがテストする候補者の数です！