Backtracking is a general algorithm for finding all (or some) solutions to some computational problems.

Leetcode backtracking problem collection (1)

  • 46.Permutations
  • 78.Subsets
  • 77.Combinations
  • 39.Combination Sum
  • 22.Generate Parentheses

Difference between backtracking and DFS:

Backtracking is an algorithem, DFS is a specific form of backtracking related to searching tree structures.
DFS handles an explicit tree.While Backtracking handles an implicit tree.

How to backtrack?

Backtracking actually is searching a decision tree. Three keys:

  1. path: decisions you made
  2. choices: remaining options
  3. terminal criteria: reach the end of decision tree.

Template

1
2
3
4
5
6
7
8
9
res = []
def backtracking(path, choices):
    if terminal criteria:
        res.append(path)
        return
    for choice in choices:
        make decision
        backtracking(path, choices)
        cancel choose

46. Permutations

Technically backtracking is brute force, it will exhaust all possible solutions. 

1
2
3
4
5
6
7
8
9
10
11
12
13
def permute(self, nums: List[int]) -> List[List[int]]:
    def backtrack(nums, path):
        if len(nums) == len(path):
            res.append(path)
            return
        for i, n in enumerate(nums):
            if n in path:
                continue
            backtrack(nums, path + [n])
    
    res = []
    backtrack(nums, [])
    return res

78. Subsets

pre-order search.

1
2
3
4
5
6
7
8
9
10
11
def subsets(self, nums: List[int]) -> List[List[int]]:
        
    def backtrack(start, path):
        res.append(path)
        for i in range(start, len(nums)):
            backtrack(i + 1, path + [nums[i]])
        return
    
    res = []
    backtrack(0, [])
    return res

77. Combinations

The same as finding subsets, but only attach path when length hit k.

1
2
3
4
5
6
7
8
9
10
11
12
def combine(self, n: int, k: int) -> List[List[int]]:
        
    def backtrack(start, path):
        if len(path) == k:
            res.append(path)
            return
        for i in range(start, n + 1):
            backtrack(i + 1, path + [i])
    
    res = []
    backtrack(1, [])
    return res

39. Combination Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        
    def backtrack(start, path, cur):
        if cur > target:
            return
        if cur == target:
            res.append(path)
            return
        
        for i in range(start, len(nums)):
            n = nums[i]
            backtrack(i, path + [n], cur + n)
    
    res = []
    backtrack(0, [], 0)
    return res

22. Generate Parentheses

use left and right to log reamining number of bracket. Remaining right should always greater or equal to left.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def generateParenthesis(self, n: int) -> List[str]:
        
    def backtrack(left, right, path):
        # right bracket should more than left
        if right < left or left < 0 or right < 0:
            return
        if right == 0 and left == 0:
            res.append(path)
        backtrack(left - 1, right, path + '(')
        backtrack(left, right - 1, path + ')')
    
    res = []
    backtrack(n, n, '')
    return res

Reference