Skip to main content

Recursion and Backtracking

Common Questions

Subsets
Combinations
Permutation
N Queen Problem

Backtracking Template from labuladong

def backtrack(nums, start, track):
    # End condition
    if (end condition):
        result.add(track)
        return
    for i in nums[start:]:
        track.append(i)
        backtrack(nums, i+1, track)
        track.pop()

Time Complexity: O(N!).

Space Complexity: O(n).

tip

For more details on time and space complexity, read this post: https://stackoverflow.com/questions/65526515/how-to-identify-time-and-space-complexity-of-recursive-backtracking-algorithms-w

Example Solutions​

Combinations​

Solution: Backtracking​

combinations
def combine(self, n, k):
    res = []
    self.backtrack(n, k, 1, res)
    return res

def backtrack(self, n, k, start, track, res):
    if len(track) == k:
        res.append(track)
        return
    for i in range(start, n+1): # Order matters, increasing
        track.append(i)
        self.backtrack(n, k, i + 1, track, res)
        track.pop()

Permutations​

Solution: Backtracking​

permutations
def permute(self, nums):
    res = []
    self.backtrack(nums, [], res)
    return res

def backtrack(self, nums, track, res):
    if len(track) == len(nums):
        res.append(track)
        return
    for i in nums: # Order does not matter so we loop through entire array
        if i in track: # Exclude numbers already in track
            continue
        track.append(i)
        self.backtrack(nums, track, res)
        track.pop()

Subsets II​

Solution: Backtracking​

def subsetsWithDup(nums):
    res = []
    nums.sort() # Sort to get power of set
    self.backtrack(nums)

def backtrack(nums, start, track, res):
    res.append(track)
    for i in range(start, len(nums)):
        if i > start and nums[i] == nums[i-1]: # IMPT: Skips over duplicate subsets
            continue
        track.append(nums[i])
        self.backtrack(nums, i + 1, track, res)
        track.pop()