The basics of 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). Backtracking According to the study on , 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. fundamental backtracking The backtracking algorithm owes its success and effectiveness to the . 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. depth-first search method In general, there are three common types of problems that backtracking solves: problems - finding a feasible solution; Decision problems - finding the best solution possible; Optimization problems - finding all the feasible solutions. Enumeration Now, let's move on from theory to practice and have a look at by the backtracking techniques. Noteworthy is that both of the problems were taken from real job interviews, and they are included in the list. 2 algo problems solved Leetcode Top Interview Questions Subsets Problem description Given an integer array of unique elements, return . The solution set must not contain duplicate subsets. Return the solution in any order. nums all possible subsets (the power set) Input: nums = [0,1,2] Output: [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]] Idea It is common knowledge that the of a set is considered to be the set of all subsets of S, including both the empty set and itself. The power set of is graphically illustrated below: power set S S {0,1,2} The most direct way is to: compute all the subsets that do not contain a particular element (which could be any single element); U compute all the subsets that do contain the required element. V After it, each subset set must appear either in or in , providing us with the final result of . The construction is recursive, and the is when the input set is empty, in which case we return an empty list. U V U⋃V base case Example Now, it’s the right moment to study the example: Let = [0,1,2]. Pick any element, e.g., 0. nums First, we recursively compute all subsets of {1,2}. To do this, we select 1. This leaves us with {2}. 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}}. Solution 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); } } } Performance all the subsets are generated and further copied to the output list using . The number of recursive calls, , satisfies the recurrence , which solves to . Since we spend time within a call, the time complexity is . The time complexity: O(N×2^N) C(n) C(n) = 2C(n - 1) C(n) = (2^N) O(N) O(N×2^N) is calculated by the following formula: . We are using the space to maintain , and are modifying in-place with backtracking. The space complexity O(N) O(N) cur cur Permutations Problem description Given an array of distinct integers, return . The answer can be returned in any order. nums all the possible permutations Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Idea It is generally known that every permutation of begins with one of . The basic idea here is to generate all permutations starting with , then all permutations starting with , and so on. Computing all permutations starting with means computing all permutations of , which suggests the use of recursion. A A[0], A[1], ..., A[n-1] A[0] A[1] A[0] A[1:n-1] To compute all permutations starting with , we swap with and compute all permutations of the updated . As we go on, we restore the original state before embarking on the computation of all permutations that start with , and so on. A[1] A[0] A[1] A[1:n-1] A[2] Example 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). Solution 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; } } Performance The time complexity is , since there are permutations, and we spend 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|). 0(n×n!) n! 0(n) Conclusion 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 “ ” 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. backtracking List of references Aziz, Adnan; Prakash, Amit; Lee, Tsung-Hsien (2012). “Elements of Programming Interviews in Java” Gurari, Eitan (1999). “CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms” “Introduction to Backtracking - Data Structure and Algorithm Tutorials” - GeeksforGeeks Upadhyay, Soni (2023). “What is Backtracking Algorithm? Types, Examples & its Application” Zibbu, Shirsh (2018). “Sudoku and Backtracking”
