Python Standard Templated Backtracking


  • 0
    W

    Solved with Backtracking that looks a lot like N-Queen, Subsets and Permutations.

    A little tweak on the parameter k since Choosing k numbers from n is sort of equivalent to
    choosing n-k numbers from n numbers. Can be a lot faster in cases where k is very close to n. Say n = 20, k = 18. We actually just need to pick out 2 numbers.
    '''

    def combine(self, n, k):
        _k = k
        if k > n / 2 + 1:
            k = n - k
        ret = []
        self.dfs(n, k, [], ret)
        if _k != k:
            temp = []
            for i in ret:
                temp.append([j for j in range(1, n + 1) if j not in i])
            return temp
        return ret
    
    def dfs(self, n, k, cur, ret):
        if len(cur) == k:
            ret.append(cur[::])
            return
        temp = 0 if not cur else cur[-1]
        for i in range(1+temp, n+1):
            cur.append(i)
            self.dfs(n, k, cur, ret)
            cur.pop()
    

    '''


Log in to reply
 

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