Backtracking Algorithm

The template for backtracking is as follows:

result = []
def backtrack(path, choice_list):
    if end_condition_met:
        result.add(path)
        return

    for choice in choice_list:
        # make a choice
        backtrack(path, choice_list)
        # !!! undo

Permutations (Leetcode 46)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        self.results = []
        tracks = []
        used = [False] * len(nums)
        self.backtrack(nums, tracks, used)

        return self.results



    def backtrack(self, nums, tracks, used):

        if len(tracks) == len(nums):
            self.results.append(tracks.copy())
            return 

        for i in range(len(nums)):
            if used[i]:
                continue

            tracks.append(nums[i])
            used[i] = True
            self.backtrack(nums, tracks, used)

            tracks.pop()
            used[i] = False

Subsets (Leetcode 78)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

        self.res = []
        tracks = []
        start = 0

        self.backtrack(nums, tracks, start)

        return self.res

    def backtrack(self, nums, tracks, start):

        self.res.append(tracks.copy())

        for i in range(start, len(nums)):
            tracks.append(nums[i])
            self.backtrack(nums, tracks, i+1)
            tracks.pop()

Combinations (Leetcode 77)

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.res = []
        tracks = []
        start = 0

        nums = range(1, n+1)

        self.backtrack(nums, tracks, start, k)

        return self.res

    def backtrack(self, nums, tracks, start, k):

        if len(tracks) == k:
            self.res.append(tracks.copy())
            return

        for i in range(start, len(nums)):
            tracks.append(nums[i])
            self.backtrack(nums, tracks, i+1, k)
            tracks.pop()

Subsets II (Leetcode 90)

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

        self.res = []
        tracks = []
        start = 0

        nums.sort()

        self.backtrack(nums, tracks, start)

        return self.res

    def backtrack(self, nums, tracks, start):

        self.res.append(tracks.copy())

        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue

            tracks.append(nums[i])
            self.backtrack(nums, tracks, i+1)
            tracks.pop()

Combination Sum II (Leetcode 40)

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        tracks = []

        candidates.sort()

        self.backtrack(candidates, tracks, target, 0)

        return self.res


    def backtrack(self, candidates, tracks, target, start):
        if target == 0:
            self.res.append(tracks.copy())
            return

        for i in range(start, len(candidates)):
            if candidates[i] > target:
                continue

            if i > start and candidates[i] == candidates[i-1]:
                continue

            tracks.append(candidates[i])

            self.backtrack(candidates, tracks, target - candidates[i], i+1)
            tracks.pop()

Permutations II (Leetcode 47)

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        self.res = []
        tracks = []
        used = [False] * len(nums)
        nums.sort()

        self.backtrack(nums, tracks, used)

        return self.res


    def backtrack(self, nums, tracks, used):

        if len(nums) == len(tracks):
            self.res.append(tracks.copy())

        for i in range(len(nums)):
            if i>0 and nums[i-1] == nums[i] and (not used[i-1]):
                continue
            if used[i]:
                continue
            tracks.append(nums[i])
            used[i] = True

            self.backtrack(nums, tracks, used)
            tracks.pop()
            used[i] = False

Combination Sum (Leetcode 39)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        self.res = []
        tracks = []
        self.backtrack(candidates, tracks, target, 0)

        return self.res


    def backtrack(self, candidates, tracks, target, start):

        if target == 0:
            self.res.append(tracks.copy())

        for i in range(start, len(candidates)):
            if candidates[i] > target:
                continue

            tracks.append(candidates[i])
            self.backtrack(candidates, tracks, target - candidates[i], i)
            tracks.pop()