Introduction
Backtracking is an algorithmic technique used for finding solutions to a problem recursively by incrementally building the solution by considering all potential combinations and abandoning the ones that do not satisfy the problem constraints.
Backtracking algorithms are based on the DFS (Depth First Search) approach.
Backtracking is generally used for three types of problems:
- Decision Problem: Searching for a feasible solution.
- Optimization Problem: Searching for the best solution.
- Enumeration Problem: Searching for all feasible solutions.
Examples
Get all subsets (Enumeration Problem)
Approach 1:
The idea here is to recursively call the same function to consider all subsets. For each index, consider two cases: one including the current element and one excluding the current element.
Pseudocode:
- If reached end of array, add current subset to list of subsets
- Include current element in subset
- Add current element
- Get all subsets after current index
- Exclude current element in subset
- Remove current element
- Get all subsets after current index
Approach 2:
The idea here is to recursively call the same function to consider all subsets.
For each index:
- Add current subset
- Iterate over all the elements from that index till the end. In each iteration:
- Include an element in the subset
- Recursively call with the next index
- Exclude last inserted element
Check if subset sum is equal to target (Decision Problem)
The idea here is to recursively call the same function to consider all subsets and see if sum of subset is equal to target or not. For each index, consider two cases: one including the current element and one excluding the current element.
Find subset with minimum sum (Optimization Problem)
The idea here is to recursively call the same function to consider all subsets and see if sum of subset is less than minimum or not. For each index, consider two cases: one including the current element and one excluding the current element.
Get all permutations (Enumeration Problem)
The idea here is generate each permutation from the previous permutation.
Example
getAllPermutations("abcd"):
- a + getAllPermutations("bcd")
- ab + getAllPermutations("cd")
- abc + getAllPermutations("d") => abcd
- abd + getAllPermutations("c") => abdc
- ac + getAllPermutations("bd")
- acb + getAllPermutations("d") => acbd
- acd + getAllPermutations("b") => acdb
- ad + getAllPermutations("bc")
- adb + getAllPermutations("c") => adbc
- adc + getAllPermutations("b") => adcb
- b + getAllPermutations("acd")
- ba + getAllPermutations("cd")
- bac + getAllPermutations("d") => bacd
- bad + getAllPermutations("c") => badc
- bc + getAllPermutations("ad")
- bca + getAllPermutations("d") => bcad
- bcd + getAllPermutations("a") => bcda
- bd + getAllPermutations("ac")
- bda + getAllPermutations("c") => bdac
- bdc + getAllPermutations("a") => bdca
- c + getAllPermutations("abd")
- ca + getAllPermutations("bd")
- cab + getAllPermutations("d") => cabd
- cad + getAllPermutations("b") => cadb
- cb + getAllPermutations("ad")
- cba + getAllPermutations("d") => cbad
- cbd + getAllPermutations("a") => cbda
- cd + getAllPermutations("ab")
- cda + getAllPermutations("b") => cdab
- cdb + getAllPermutations("a") => cdba
- d + getAllPermutations("abc")
- da + getAllPermutations("bc")
- dab + getAllPermutations("c") => dabc
- dac + getAllPermutations("b") => dacb
- db + getAllPermutations("ac")
- dba + getAllPermutations("c") => dbac
- dbc + getAllPermutations("a") => dbca
- dc + getAllPermutations("ab")
- dca + getAllPermutations("b") => dcab
- dcb + getAllPermutations("a") => dcba
Complexity Analysis
Time Complexity
Finding the time complexity of a backtracking solution is pretty difficult. We can estimate the time complexity by finding the number of different states that our recursive code will compute and see how many operations are happening in each recursive call. Calculating the exact runtime will require finding the recurrence relation and using any of the analysis techniques.
Example (Subset Problem)
- Number of states: 2^n
- Number of operations in each call: 1 in general and n in terminating case (adding array to result)
- Total Time Complexity: O(n * 2^n)
Space Complexity
Space Complexity can be calculated based on how much data we are storing for each state. If it is not an enumeration problem then we do not maintain each state and so the space complexity would be the maximum space required for any state.
For the Subset Problem, we are storing max n elements for each state and so the space complexity is O(n * 2^n).
Should you use backtracking to solve a given problem?
- Any problem that has clear and well-defined constraints on any objective solution that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution can be solved using backtracking.
- Inspite of that, not all such problems should be solved with backtracking. Backtracking solution are generally exponential in nature and might not provide the most optimized solution.
- If a problem can be solved using some other non-exponential algorithmic technique like Dynamic Programming, Greedy Algorithm, etc, then backtracking should be avoided.
- If there is no such solution available for a problem then we might have to use backtracking.
Applications
Some common problems that can be solved using backtracking:
- Finding all the subsets of an array.
- Finding all the subsets of an array that satisfy a particular constraint (Example: a defined sum of the subset).
- Finding all the permutations of a string.
- Creating a sudoku solver.
- Helping search contacts by finding all letter combinations from telephone buttons given a few digits.
- Finding the path to get out of a maze.
- Knapsack Problem/Resource Allocation.
It is also extensively used in problems related to trees and graphs.
Sudoku solved using Backtracking
