backtracking 파이썬 시간 제한에 도달했습니다 (조합 합계) 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 

의 항목은, 불필요한 테스트 조합을 대표하고 다른 프로그램에서 테스트하지 않았습니다.

추가 후보자가 생성 된 결과로 가능한 솔루션마다 중복 시간을 투자하여 중복되지 않도록해야합니다. 그것은 각각의 후보가 고유하기 때문에 다른 솔루션에서는 필요하지 않습니다. 이 추가 테스트는 런타임에 추가하여 더욱 악화시킵니다. 그러나 해결해야 할 주요 사항은 테스트하는 응시자의 수입니다!