[Algorithm] Topic 5: Backtracking

Authored by Tony Feng

Created on April 4th, 2022

Last Modified on April 4th, 2022

Understanding Backtracking

Intro

A backtracking algorithm is a problem-solving algorithm that uses a brute-force approach for finding the desired output.
The term backtracking suggests that if the current solution is not suitable, then go back and try other solutions.
Backtracking uses recursion to discover all of the possibilities until we get the best end result for the problem.
State Space Tree
- A space state tree is a tree representing all the possible states (solution or nonsolution) of the problem from the root as an initial state to the leaf as a terminal state.
- In combinatorial search problems, search space is in the shape of a tree.

Types of Problems

Decision Problem: Search for a feasible solution
Optimization Problem: Search for the best solution
Enumeration Problem: Find all feasible soutions

Template

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


# Pseudocode
function backtracking(node, state):
    if state is a solution:
        report(state) # e.g. add state to final result list
        return

    for child in children:
        if child is a part of a potential solution:
            state.add(child) # make move
            backtracking(child, state)
        state.remove(child) # backtrack

Examples

Leetcode 46 Permutations

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        
        def backtrack(path, cnt):
            if cnt == 0:
                ans.append(path[:]) # Copy the content instead of the reference
                return
            
            for item in nums:
                if not item in path:
                    path.append(item)
                    backtrack(path, cnt-1)
                    path.pop()
        
        backtrack([],len(nums))
        return ans

Leetcode 77 Combinations

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:

        ans = []
        nums = list(range(1, n+1))
        
        def backtrack(path, m):
            if len(path)==k:
                ans.append(path[:])
                return
            
            for i in range(m, len(nums)):
                path.append(nums[i])
                backtrack(path, i+1)
                path.pop()
        
        backtrack([],0)
        return ans

Leetcode 78 Subsets

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]
        
        def backtrack(path, lmt, index):
            if len(path) == lmt:
                ans.append(path[:])
                return
            
            for id in range(index, len(nums)):
                path.append(nums[id])
                backtrack(path, lmt, id+1)
                path.pop()
        
        for i in range(1, len(nums)+1):
            backtrack([], i, 0)
        return ans

Leetcode 22 Generate Parentheses

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        left, right = 0, 0
        ans = []
        
        def backtrack(path, l, r):
            if l == n and r == n:
                path = ("").join(path)
                ans.append(path[:])
                return
            
            # The number of right bracket cannot exceed that of left bracket.
            if l < r:
                return
            
            if l <= n:
                path.append("(")
                backtrack(path, l+1, r)
                path.pop()
            
            if l > r:
                path.append(")")
                backtrack(path, l, r+1)
                path.pop()
            
        
        backtrack([], left, right)
        return ans

Understanding Backtracking

Intro

Types of Problems

Template

Examples

Leetcode 46 Permutations

Leetcode 77 Combinations

Leetcode 78 Subsets

Leetcode 22 Generate Parentheses

Reference