Backtracking has proven itself to be a universal algorithmic technique that can be applied while solving all kinds of computational problems, from the most primitive (such as counting all possible paths between two vertices) to the most complex ones (such as finding all Hamiltonian paths or solving the N Queen problem).
According to the fundamental study on backtracking, it can be defined as an improvement to the brute force approach. In other words, the basic idea behind the backtracking technique is the search for a solution to a particular problem among all the options available.
The backtracking algorithm owes its success and effectiveness to the depth-first search method. When the algorithm initiates its extensive search for solutions, it promptly applies the abounding function, making it possible to determine whether a proposed solution meets the constraints set. In case the answer is positive, the algorithm continues its search. If this is not the case, the algorithm removes the branch and simply returns to the previous level.
In general, there are three common types of problems that backtracking solves:
Now, let's move on from theory to practice and have a look at 2 algo problems solved by the backtracking techniques. Noteworthy is that both of the problems were taken from real job interviews, and they are included in the Leetcode Top Interview Questions list.
Given an integer array nums
of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
Input: nums = [0,1,2]
Output: [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]
It is common knowledge that the power set of a set S is considered to be the set of all subsets of S, including both the empty set and S itself. The power set of {0,1,2} is graphically illustrated below:
The most direct way is to:
After it, each subset set must appear either inU or in V, providing us with the final result of U⋃V. The construction is recursive, and the base case is when the input set is empty, in which case we return an empty list.
Now, it’s the right moment to study the example:
nums
= [0,1,2]. Pick any element, e.g., 0.
Now, we pick 2 and get to the base case. -> {}
Returning from the recursive calls:
3. So, the set of subsets of {2} is {} union with {2}, i.e., {{}, {2}}. 2. The set of subsets of {1, 2} is then {{}, {2}} union with {{1}, {1, 2}}, i.e., {{}, {2}, {1}, {1, 2}}.
The set of subsets of {0,1,2} is then {{}, {2}, {1}, {1, 2}} union with {{0}, {0, 2}, {0, 1}, {0, 1, 2}}, i.e., {{}, {2}, {1}, {1, 2), {0}, {0, 2}, {0, 1}, {0, 1, 2}}.
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
backtrack(nums, 0, new LinkedList<>(), ans);
return ans;
}
void backtrack(int[] nums, int i, List<Integer> cur, List<List<Integer>> ans){
ans.add(new ArrayList<>(cur));
for (int j = i; j<nums.length; j++){
cur.add(nums[j]);
backtrack(nums, j + 1, cur, ans);
cur.remove(cur.size() - 1);
}
}
}
The time complexity: all the subsets are generated and further copied to the output list using O(N×2^N). The number of recursive calls, C(n), satisfies the recurrence C(n) = 2C(n - 1), which solves to C(n) = (2^N). Since we spend O(N) time within a call, the time complexity is O(N×2^N).
The space complexity is calculated by the following formula: O(N). We are using the O(N) space to maintain cur
, and are modifying cur
in-place with backtracking.
Given an array nums
of distinct integers, return all the possible permutations. The answer can be returned in any order.
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
It is generally known that every permutation of A begins with one of A[0], A[1], ..., A[n-1]. The basic idea here is to generate all permutations starting with A[0], then all permutations starting with A[1], and so on. Computing all permutations starting with A[0] means computing all permutations of A[1:n-1], which suggests the use of recursion.
To compute all permutations starting with A[1], we swap A[0] with A[1] and compute all permutations of the updated A[1:n-1]. As we go on, we restore the original state before embarking on the computation of all permutations that start with A[2], and so on.
For instance, for the array (1, 2, 3), we would first generate all permutations starting with 1.
This implies generating all permutations of (2, 3).
Next, we find all permutations of (2, 3) starting with 2. Given that (3) is an array of length 1, it has the only possible permutation. The implication of this is that (2, 3) has a single permutation starting with 2.
After that, we look for permutations of (2, 3) starting with 3, which can be executed by swapping 2 and 3. Consequently, we will find out that there is a single permutation of (2, 3) starting with 3, namely, (3, 2).
Hence, there are two permutations starting with 1: (1,2,3) and (1,3,2). To find all permutations starting with 2, we swap 1 with 2 and get two permutations again: (2,1,3) and (2,3,1).
The last two permutations we add are (3,2,1) and (3,1,2). In total, there are six permutations: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,2,1) and (3,1,2).
class Solution {
List<List<Integer>> result;
public List<List<Integer>> permute(int[] nums) {
Arrays.sort(nums);
result = new ArrayList<>();
permute(0, nums);
return result;
}
private void permute(int i, int[] nums){
if (i == nums.length - 1){
copyToResult(nums);
}
for (int j = i; j<nums.length; j++){
swap(i,j,nums);
permute(i+1,nums);
swap(j,i,nums);
}
}
private void copyToResult(int[] nums){
List<Integer> list = new ArrayList<>();
for (int num: nums){
list.add(num);
}
result.add(list);
}
private void swap(int i, int j, int[] nums){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
The time complexity is 0(n×n!), since there are n! permutations, and we spend 0(n) time to store each one. Having studied this example, we can observe that backtracking only visits each state once, which is why its time complexity should be similar to the graph traversal of O(|V|+|E|).
Summing up the above, backtracking is definitely a perfect algorithmic technique for solving both subset and permutation problems. With the help of its depth-first search method, the backtracking algorithm will inevitably find the required solution in strict compliance with all given constraints.
Since 1950, when the term “backtracking” was coined by D. H. Lehmer, an American mathematician, backtracking managed to handle a wide range of practice problems, starting from printing all paths from a given source to a destination and finishing with finding the shortest safe route in a path with landmines. In this regard, the next time you deal with either permutations or subsets, I strongly recommend that you use the backtracking algo pattern.