Skip to main content

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​