What is Backtracking?
At its simplest, backtracking is a technique for solving problems by trying different possibilities and discarding them when they don’t lead to a solution. It’s a form of trial and error—but smarter.
Backtracking involves recursively exploring all possible options in a solution space and "backtracking" when you reach a state that doesn't work or can't lead to a solution.
In short:
Backtracking = Trying options and retracing when things go wrong.
How Does Backtracking Work?
Backtracking is a step-by-step process that involves:
Choosing an option: You start by making an initial decision or taking an initial step.
Exploring further: You continue to take additional steps based on the previous choice, recursively trying out new possibilities.
Checking for validity: After each new decision, you check if the current path leads to a valid solution.
Backtracking: If a step leads to an invalid solution or dead-end, you backtrack, undoing your previous step, and try a different option.
Important Problem on LeetCode
Below code pattern can be used to solve most of the problems of backtracking, with just minimal changes based on problem.
Permutation: A permutation is a rearrangement of all the elements of an array.
public List<List<Integer>> permute(int[] nums) { // Initialize the result list to store all permutations List<List<Integer>> result = new ArrayList<>(); // Temporary list that will hold the current permutation List<Integer> temp = new ArrayList<>(); // Start the recursive process to generate all permutations generate(result, temp, nums); // Return the list containing all generated permutations return result; } private void generate(List<List<Integer>> result, List<Integer> temp, int[] nums){ // Base case: if the temporary list has the same size as the input array (a full permutation) if(temp.size() == nums.length){ // Add the current permutation to the result list result.add(new ArrayList<>(temp)); }else{ // Iterate over all elements in the nums array for(int i = 0; i < nums.length; i++){ int curr = nums[i]; // Get the current element // Check if the current element has already been added to the temporary list (prevents duplicates) // temp.contains(curr) takes O(n) time, so this can be inefficient for larger arrays if(!temp.contains(curr)){ // Add the current element to the temporary list temp.add(curr); // Recursively generate permutations with the updated temporary list generate(result, temp, nums); // Backtrack: remove the last element (undo the choice) temp.remove(temp.size() - 1); } } } }Combination Sum
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// Result list to store all valid combinations
List<List<Integer>> result = new ArrayList<>();
// Start the recursive process with an empty temporary list, and an index of 0
generate(result, new ArrayList<>(), candidates, target, 0);
// Return the result containing all the valid combinations
return result;
}
private static void generate(List<List<Integer>> result, List<Integer> temp, int[] nums, int target, int index) {
// Base case: if target becomes negative, it's an invalid combination (prune this path)
if (target < 0) {
return;
}
// If the target becomes 0, we've found a valid combination, so add it to the result
else if (target == 0) {
result.add(new ArrayList<>(temp));
}
// Recursively explore all combinations starting from the current index
else {
// Loop through the candidates starting from the given index
for (int i = index; i < nums.length; i++) {
int curr = nums[i]; // The current number in the array
// Add the current number to the temporary list (to form a potential combination)
temp.add(curr);
// Recursively call the function to explore the remaining target with the current number included
// Notice that the index is not incremented because we can reuse the same element
generate(result, temp, nums, target - curr, i); // Pass the same index (i) to allow repetition of numbers
// Backtrack: remove the last added number to try other possibilities
temp.remove(temp.size() - 1);
}
}
}Generate Parentheses, LC: 22
Combination Sum, LC: 39,40
Permutations, LC: 46, 47
Subsets, LC: 78, 90
Word Ladder, LC: 126
When to Use Backtracking?
Backtracking is ideal when:
Combinatorial problems: Find combinations or permutations of a set.
Constraint satisfaction problems: Ensure that solutions meet certain conditions (e.g., N-Queens).
Searching large solution spaces: Explore multiple possibilities efficiently, pruning invalid paths along the way.
When NOT to use backtracking?
When the solution space is too large and pruning isn’t possible.
When the problem lacks constraints that require backtracking.
When performance (memory/time) is critical and backtracking would be too slow.
Conclusion
Backtracking is an efficient and versatile technique for problems involving combinations, permutations, and constraint satisfaction. By understanding how it works and when to use it, you can apply this approach to a wide range of problems, from Combination Sum to Sudoku and N-Queens.
Moreover, mastering backtracking is essential for interviews, as it demonstrates your ability to solve complex problems efficiently while thinking recursively and optimizing the search process.
If you found this post helpful, consider subscribing for more updates or following me on LinkedIn, and GitHub. Have questions or suggestions? Feel free to leave a comment or contact us. Happy coding!!