A review on backtracking algorithm.

Base template

Find follwing 3 elements in the tree model:

what is the track (edges from root down to the leaf)
what is the possible options (possible children in each node, optimizing on cutting unwanted edges in advance)
what is the ending criteria (how to tell the leaf is reached during tracking)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


res = []
track = []
def backtrack(options):
    if track.meet_requirement():
        res.append(track)
        return
    for opt in options:
        track.add(opt) # options.remove(opt)
        backtrack(options)
        track.remove(opt) # options.add(opt)

Alternatives

No duplicated elements, no duplicated selection

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


# combination/subset
def backtrack(nums: List[int], start: int):
    for i in range(start, len(nums)):
        # select
        track.append(nums[i])
        # next layer in tree
        backtrack(nums, i + 1)
        # restore
        track.pop()

# permutation
def backtrack(nums: List[int]):
    for i in range(len(nums)):
        # cutting edge
        if used[i]:
            continue
        # select
        used[i] = True
        track.append(nums[i])
        # next layer
        backtrack(nums)
        # restore
        track.pop()
        used[i] = False

Duplicable elements, no duplicated selection

 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
29
30
31


nums.sort()

# combination/subset
def backtrack(nums: List[int], start: int):
    for i in range(start, len(nums)):
        # cutting edge
        if i > start and nums[i] == nums[i-1]:
            continue
        # select
        track.append(nums[i])
        # next layer in tree
        backtrack(nums, i + 1)
        # restore
        track.pop()

# permutation
def backtrack(nums: List[int]):
    for i in range(len(nums)):
        # cutting edge
        if used[i]:
            continue
        if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
            continue
        # select
        used[i] = True
        track.append(nums[i])
        # next layer
        backtrack(nums)
        # restore
        track.pop()
        used[i] = False

No duplicated elements, duplicable selection

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


# combination/subset
def backtrack(nums: List[int], start: int):
    for i in range(start, len(nums)):
        # select
        track.append(nums[i])
        # next layer in tree
        backtrack(nums, i)
        # restore
        track.pop()

# permutation
def backtrack(nums: List[int]):
    for i in range(len(nums)):
        # select
        track.append(nums[i])
        # next layer
        backtrack(nums)
        # restore
        track.pop()

Algo Review: backtracking

Base template

Alternatives

No duplicated elements, no duplicated selection

Duplicable elements, no duplicated selection

No duplicated elements, duplicable selection

See Also