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

Question

my question relates to this problem https://leetcode.com/problems/combination-sum-iii/discuss/ and all backtracking problems.

My question is: why is my code (really similar to other people's answers) always have a larger run time than theirs?

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)

other people's code that passed the time limit:

# @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

The main difference and slowdown is due to your code testing many more combinations than the other solution. You generate all combinations of numbers, which leads you to test the "same" combination multiple times, whereas the other solution only generates each possible candidate once, by only allowing next number in the sequence to be equal or larger than the previous one.

Look at the following, limited list of candidates, where the range of numbers is limited to be from 1 to 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

The entries with <- represent combinations that you test, which are unnecessary, and not tested by the other program.

In addition, and as a consequence of your extra candidates generated, you also need to spend extra time on each possible solution, to make sure it is not already in the solution set (to avoid duplicates). That is not needed by the other solution, as there each candidate is unique. This extra test also adds to your run time, to make it even worse. However, the main thing to fix is the number of candidates you test!