[Leetcode Patterns] Backtracking
Backtracking is used in specific cases of DFS. Global variable / parameter may be modified across different level of search. However, when search returns, the variable / parameter needs to be at original state for the new search, where backtracking should occur.
The key of backtracking is good choice of parameters.
combination, subset, permutation
Use index or some val for accumulation to forward the DFS, and an array to store the searched node. The base is case specific, or index / array reaching n. Decremeting given arr as parameter may also be available, but inefficient for space since this copies new arr in each new DFS.
binary path for choosing node
Need not to calculate or complare elm so only consider exclude or include current, like binary path. After the inclusion, pop array as backtracking. Base is array len. Cannot address problems that index no use. Time complexity: O(2^n)
e.g. Combinations, Subsets
# binary path
def h(i, arr):
if arr meets requirement: push arr copy, return
if index / future index no longer valid: return
h(i+1, arr)
arr.append(nums[i])
h(i+1, arr)
arr.pop()When filtering duplicate is required, binary path is inconvenient as filtering may require comparing acorss more than 1 position, a quite different pattern with binary path. This is often addressed via loop.
loop
An intuitive way of searching. Works for almost all cases. Convenient for making adjustment like prunning or filtering duplcate. Often use index to forward DFS, where incrementing index can work as the new start of subarray (though no array is actually created). However, if node can be reused, index
is no use of parameter, and other parameter shall be designed for base. Time complexity: O(n²)
e.g. Combinations, Combination Sum, Combination Sum II, Permutations, Subsets
# elm not reusable
def h(i, arr):
base according to index
for j in range(i, n):
arr.append(nums[j])
h(j+1, arr)
arr.pop()# elm reusable
def h(val, arr):
base according to value like accumulation
for j in range(i, n):
curr = nums[j]
h(val + curr, arr + [curr])
# val and arr must be kept in "same state", meaning when val increments curr, arr must include curr, so cannot use append then pop like the former path
Common technique
# prun
Only works if sort first
In loop traverse, break if curr cannot meets requirement (the rest can neither meet as > curr).# filter to waive duplicate
Only works if sort first
In loop traverse, compare curr with stored elm in arr or prev. When ciolating condition, continue as this would be addressed in other time.# swap
Use in permutation where same elms with different sequence are considered different. In loop traverse, rather than pushing [j] dicrectly, swap i with j and push i. Restore the swap after backtracking. By doing so, target array continues to push elm with different sequence.
* subarray
Subarray is defined as strictly contiguous elms in original array, thus different from combination / subset / permutation above. The contiguous property disables the include-exclude-include_new form. Hence, to get subarray needs no backtracking. A nested loop with forwarding init points can work.
# iterative
for i in range(n):
subarray = []
for j in range(i, n):
subarray.append(nums[j])
push subarray here (if not violating constraint)
