Why my code always causes Time Limit Exceeded


  • 0
    E

    This is my code:

    class Solution(object):
        def combine(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: List[List[int]]
            """
            res = []
            def back(res, k, start, com = []):
                if not k:
                    res.append(com)
                    return
                for i in range(start, n + 1):
                    back(res, k-1, i + 1, com + [i])
            back(res, k, 1)
            return res
    

    i think it almost same with other algorithms written in java or c++,but it cause tle when pass (20, 16),how can improve my code?


  • 0
    E

    all right i know where is wrong
    the code above will backtrack too manys times which might be useless
    I should add a conditional judgment before backtrack

    class Solution(object):
        def combine(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: List[List[int]]
            """
            res = []
            def back(res, k, start, com = []):
                if k == 0:
                    res.append(com)
                    return
                for i in range(start, n + 1):
                    if n - i >= k - 1:
                        back(res, k-1, i + 1, com + [i])
            back(res, k, 1)
            return res
    

    i can backtrack while i have enough num to add to the comb


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.