Backtrack Summary: General Solution for 10 Questions!!!!!!!! Python (Combination Sum, Subsets, Permutation, Palindrome)


  • 1
    D

    For Java version, please refer to isssac3's answer.

    If you find it helpful, please vote to let more people see this post. Besides, it would be great if you find other questions could be solved use this general solution. Please make a comment below.

    39. Combination Sum
    https://leetcode.com/problems/combination-sum/

        def combinationSum(self, candidates, target):
            def backtrack(tmp, start, end, target):
                if target == 0:
                    ans.append(tmp[:])
                elif target > 0:
                    for i in range(start, end):
                        tmp.append(candidates[i])
                        backtrack(tmp, i, end, target - candidates[i])
                        tmp.pop()
            ans = [] 
            candidates.sort(reverse= True)
            backtrack([], 0, len(candidates), target)
            return ans
    

    40. Combination Sum II
    https://leetcode.com/problems/combination-sum-ii/

        def combinationSum2(self, candidates, target):
            def backtrack(start, end, tmp, target):
                if target == 0:
                    ans.append(tmp[:])
                elif target > 0:
                    for i in range(start, end):
                        if i > start and candidates[i] == candidates[i-1]:
                            continue
                        tmp.append(candidates[i])
                        backtrack(i+1, end, tmp, target - candidates[i])
                        tmp.pop()
            ans = []
            candidates.sort(reverse= True)
            backtrack(0, len(candidates), [], target)
            return ans
    

    78. Subsets
    https://leetcode.com/problems/subsets/

        def subsets(self, nums):
            def backtrack(start, end, tmp):
                ans.append(tmp[:])
                for i in range(start, end):
                    tmp.append(nums[i])
                    backtrack(i+1, end, tmp)
                    tmp.pop()
            ans = []
            backtrack(0, len(nums), [])
            return ans
    

    90. Subsets II
    https://leetcode.com/problems/subsets-ii/

        def subsetsWithDup(self, nums):
            def backtrack(start, end, tmp):
                ans.append(tmp[:])
                for i in range(start, end):
                    if i > start and nums[i] == nums[i-1]:
                        continue
                    tmp.append(nums[i])
                    backtrack(i+1, end, tmp)
                    tmp.pop()
            ans = []
            nums.sort()
            backtrack(0, len(nums), [])
            return ans
    

    46. Permutations
    https://leetcode.com/problems/permutations/

        def permute(self, nums):
            def backtrack(start, end):
                if start == end:
                    ans.append(nums[:])
                for i in range(start, end):
                    nums[start], nums[i] = nums[i], nums[start]
                    backtrack(start+1, end)
                    nums[start], nums[i] = nums[i], nums[start]
                    
            ans = []
            backtrack(0, len(nums))
            return ans
    

    47. Permutations II
    https://leetcode.com/problems/permutations-ii/

        def permuteUnique(self, nums):
            def backtrack(tmp, size):
                if len(tmp) == size:
                    ans.append(tmp[:])
                else:
                    for i in range(size):
                        if visited[i] or (i > 0 and nums[i-1] == nums[i] and not visited[i-1]):
                            continue
                        visited[i] = True
                        tmp.append(nums[i])
                        backtrack(tmp, size)
                        tmp.pop()
                        visited[i] = False
            ans = []
            visited = [False] * len(nums)
            nums.sort()
            backtrack([], len(nums))
            return ans
    

    60. Permutation Sequence
    https://leetcode.com/problems/permutation-sequence/

        def getPermutation(self, n, k):
            nums = [str(i) for i in range(1, n+1)]
            fact = [1] * n
            for i in range(1,n):
                fact[i] = i*fact[i-1]
            k -= 1
            ans = []
            for i in range(n, 0, -1):
                id = k / fact[i-1]
                k %= fact[i-1]
                ans.append(nums[id])
                nums.pop(id)
            return ''.join(ans)
    

    131. Palindrome Partitioning
    https://leetcode.com/problems/palindrome-partitioning/

        def partition(self, s):
            def backtrack(start, end, tmp):
                if start == end:
                    ans.append(tmp[:])
                for i in range(start, end):
                    cur = s[start:i+1]
                    if cur == cur[::-1]:
                        tmp.append(cur)
                        backtrack(i+1, end, tmp)
                        tmp.pop()
            ans = []
            backtrack(0, len(s), [])
            return ans
    

    267. Palindrome Permutation II
    https://leetcode.com/problems/palindrome-permutation-ii/
    Related to this two:
    31. Next Permutation: https://leetcode.com/problems/next-permutation/
    266. Palindrome Permutation: https://leetcode.com/problems/palindrome-permutation/

        def generatePalindromes(self, s):
            kv = collections.Counter(s)
            mid = [k for k, v in kv.iteritems() if v%2]
            if len(mid) > 1:
                return []
            mid = '' if mid == [] else mid[0]
            half = ''.join([k * (v/2) for k, v in kv.iteritems()])
            half = [c for c in half]
            
            def backtrack(end, tmp):
                if len(tmp) == end:
                    cur = ''.join(tmp)
                    ans.append(cur + mid + cur[::-1])
                else:
                    for i in range(end):
                        if visited[i] or (i>0 and half[i] == half[i-1] and not visited[i-1]):
                            continue
                        visited[i] = True
                        tmp.append(half[i])
                        backtrack(end, tmp)
                        visited[i] = False
                        tmp.pop()
                        
            ans = []
            visited = [False] * len(half)
            backtrack(len(half), [])
            return ans
    

Log in to reply
 

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