In-depth Backtracking with LeetCode Problems — Part 2
Combination and All Paths
Before reading this post, read part one first:
Backtracking with LeetCode Problems — Part 1: Introduction and Permutation
Combination
Continue from the permutation, combination refers to the combination of n things taken k at a time without repetition, the math formula C_n^k . Combination does not care about the ordering between chosen elements, such that [a, b] and [b, a] are considered as the same solution, thus only one of them can exist. Some useful formulation with combinations include C_n^k = C_n^{n-k}.
Here, we will demonstrate how we can use backtracking to implement an algorithm that just can traverse all the states and generate the power set (all possible subsets). We can see at each level, for each parent node, we would go through all of the elements in the array that has not be used before. For example, for $[]$, we get [1], [2], [3]; for [1], we need [2], [3] to get [1, 2], [1, 3]. Thus we use an index in the designed function to denote the start position for the elements to be combined. Also, we use DFS, which means the path is []->[1]->[1, 2]->[1, 2, 3], we would use recursive function because it is easier to implement and also we can spare us from using a stack to save these nodes, which can be long and it would not really bring the benefit of using iterative implementation. The key point here is after the recursive function returns to the last level, say after [1, 2, 3] is generated, we would return to the previous state (this is why it is called backtrack!! Incremental and Backtrack).
Implementation
The process is the similar to the implementation of permutation, except that we have one different variable, start. start is used to track the start index of the next candidate instead of use the usedarray to track the state of each item in the curr solution. curr.pop() is the soul for showing it is a backtracking algorithm!
Similarly, we call the following code:
a = [1, 2, 3]
n = len(a)
ans = [[None]]
ans = []
C_n_k(a, n, 2, 0, 0, [], ans)
print(ans)The output is:
[[1, 2], [1, 3], [2, 3]]Time Complexity of Combination
Because backtracking ensures efficiency by visiting each state no more than once. For the combination(subset) problem, the total nodes of the implicit search graph tree is \sum_{k=0}^{n}C_{n}^{k} =2^n. We can look it as another way, there are in total n objects, and each object we can make two decisions: inside of the subset or not, therefore, this makes 2^N.
All Paths
Backtracking technique can be naturally used in graph path traversal. One example is to find all possible paths from a source to the target. One simpler occasion is when the graph has no cycles. Backtrack technique can enumerate all paths in the graph exactly once for each.
The implementation is as follow: we still use dfs, because there has no cycles, we have no need to track the visiting state of each node. We generate the possible answer with backtracking technique through the path variable to track each state.
With the printing, we can see the whole process, path changes as the description of backtrack.
[0, 1]
[0, 1, 2]
[0, 1, 2, 4]
[0, 1, 2, 4, 3]
[0, 1, 2, 4] backtrack
[0, 1, 2, 4, 5]
[0, 1, 2, 4, 5, 6]
[0, 1, 2, 4, 5] backtrack
[0, 1, 2, 4] backtrack
[0, 1, 2] backtrack
[0, 1] backtrack
[0] backtrack
