Introduction to Backtracking

Have you ever run into these problems in your daily life?

  • For my luggage lock, what are some of the interesting password combination I can come up with? 🔐
  • For my living room, how many possible ways I can rearrange my sofa, table, speakers and TV? 📺
  • Or, yes! this is a good one, given a set of liquors and juice, what are possible cocktails I can come up with? 🍹

Backtracking#

"Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem."

Intuitions of A Backtracking Problem#

  1. The problem is about combinations, combinatorics, and permutation. Usually the problem has multiple possible solutions and it asks you to "list" or "enumerate" all the possible solutions.
  2. When you try to come up with an combination of both iteration and recursion. For example, you need to have a loop inside of a recursive function, and the loop's range depends on the function parameters:
void someRecursiveFunction(int x, int y){
/* do something... */
for(int i = 0; i < y; i++){
/* do something in the for loop... */
// call someRecursiveFunction with updated parameters
someRecursiveFunction(x, y+i);
}
/* do something else... */
}
  1. When you can prove that the solution needs a runtime of

Backtracking Generalized Solution Template#

class Solution {
/* Declare private data structures: */
private ArrayList<Integer> solutions;
public List<List<Integer>> permute(int[] nums) {
// declare private data structures
solutions = new ArrayList<>();
// call backtrack
backtrack(param1, param2);
// return results
return this.results;
}
private void backtrack(int param1, int param2){
// handle base case!
if(BaseCase qualified){
// Add current result to the solution collection
solutions.add(param2)
return;
}
for(int i = 0; i< param1; i++){
// 1. Handle edge case
if(count[i] == 0) continue;
// 2. Prepare a possible solution using some variable
result.set(level, nums[i]);
// 3. Remove used variable in step 2
count[i]--;
// 4. Call backtrack recursively
backtrack(param1, param2+1);
// 5. Add used variable in step 2 and 4 back to the set
count[i]++;
}
}
}

References#