Backtracking algorithms

What is backtracking?

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, 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.
-Wikipedia

Let’s understand this statement in a more friendly way. All backtracking problems have a solution space. If you are looking for a particular solution, it lies within the solution space. The particular solution matches the constraints put in the problem domain.
Solution space is usually a tree-shaped. At every node, you have multiple choices and you do not have any way to find which choice will lead to the solution. So, we try every choice as far as the choice is safe according to the problem domain. If no solution is found after trying all the choices, we backtrack and take the next choice at the parent of the current node.

If we explore all the paths of this solution space, it leads to exhaustive search.

However, in backtracking, we can take a decision, whether continuing the path will ever lead to a solution? If not, we will abandon the path altogether and go to the parent node and take a different choice. This is called pruning of solution space.
Moving back to the parent node in the solution space is implicitly done using recursion, that’s why exhaustive search and backtracking problems have a recursive implementation.

Backtracking is an important tool for solving constraint satisfaction problems such as 8 queens problem, Sudoku, and many other puzzles.

General problem structure of backtracking problem

There are 4 steps to solve a backtracking problem.

  1. Check if the current state is the final state if yes, then do the bookkeeping and return.
  2. If not, enumerate all the possible choices/options you have to go from here.
  3. Loop through all the choices one by one
    1. If the choice is safe, make the choice.
    2. Try to solve the problem with the choice made above.
    3. If the problem is solved, return (This is applicable only if we are interested only 1 solution)
    4. Unmake the choice we made in 3.1
  4. If we are looking for one solution and did not return from 3.3, return false, else just return.

Let’s see some problems and make sure that we understood the backtracking algorithm steps..

Example problem 1: 8 queen problem

class Solution {
    public List<List<String>> solveNQueens(int n) {
        
        char[][] board = new char[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                board[i][j] = '.';
            }
        }
        
        List<List<String>> res = new ArrayList<>();
        solve(board, 0, res, n);
        
        return res;
    }

    void solve(char [][] board, int col, List<List<String>> res, int n){
        
        /* Step 1: Check if the current state is our final step, 
           do the bookkeeping 
           In this case, we check if we considered all the columns, 
           we put the board state as a solution.
        */
        if (col >= board[0].length) {
            res.add(new ArrayList<>(formatOutput(board, n)));
        }
        
        /* Step 2: Next, enumerate all the choice. We have to try 
           each row for the current queen */
        for (int rowToTry = 0; rowToTry < n; rowToTry++) {
            //3.1 Check if the current choice for the queen is safe
            if (isSafe(board, rowToTry, col)) {
                //3.2 Make the choice
                board[rowToTry][col] = 'Q';
                //3.3 if the choice we made actually solves the problem.
                solve(board, col + 1, res, n);
                //3.4 unmaking the choice
                board[rowToTry][col] = '.';
            }
        }
        //Step 4.
        return;
    }
    
    //Auxiliary functions are specific to the domain of the problem.
    List<String> formatOutput(char[][] board, int n){
        
        List<String> l = new ArrayList<>();
        
        for(int i=0; i<n; i++){
            l.add(String.valueOf(board[i]));
        }
        return l;
    }
    
    boolean isSafe(char[][] board, int row, int col){
        
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < col; j++) {
                if(board[i][j] == 'Q' 
                  && (row + j == col + i 
                  || row + col == i + j 
                  || row == i))
                    return false;
            }
        }
        return true;
    }
}

Example problem 2: Find permutation problem

class Solution {
    public List<List<Integer>> permute(int[] nums) {
    
        List<List<Integer>> res = new ArrayList<>();
        findPermutations(nums, new ArrayList<Integer>(), res);
        return res;
    }
    
    private void findPermutations(int [] nums, List<Integer> current, 
                                 List<List<Integer>> res){
        
        /* Step 1. Check if the current state is the solution
        In this problem, if the length of the current list is equal
        to the size of the array, we have all the integers in
        the current permutation, so adds it to the result.
        */
        if(current.size() == nums.length){
            res.add(new ArrayList<>(current));
        }
        
        /* Step 2: What all choices we have, in permutations, all the
        integers are possible choice, so we will go through all of them
        */
        for(int i=0; i<nums.length; i++){
            
            /* 3.1 Check if this number is safe for the solution,
            In permutation, each number can be present only once.
            So, skipp the number if it is already in the current
            permutation.
            */
            if(current.contains(nums[i])) continue;
            
            //3.2 Make the choice, add the num in current permutation
            current.add(nums[i]);
            
            //3.3 Solve the problem with the above choice made.
            findPermutations(nums, current, res);
            
            //3.4 Unmake the choice
            current.remove(current.size()-1);
        }
        
        //4. Return;
        return;
    }
}

Example problem 3: Find subsets

class Solution {
 
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        subsetsUtil(nums, 0, new ArrayList<Integer>(), result);
        return result;
    }
    
    private void subsetsUtil(int[] nums, int index, List<Integer> current,
                                List<List<Integer>> res){
        
        /* Step 1. Check if the current state is the solution
           Every new element make a new set, so will add to the 
           subset list.
        */
        res.add(new ArrayList<>(current));
        
        /* Step 2: A set can contain an element only once,
         and order does not matter. So we will go through
          all the elements which are remaining.
        */
        for(int i=index; i<nums.length; i++){
            //3.1. Every element is safe for a subset, so no check
      
            //3.2 Make the choice, add each
            current.add(nums[i]);
            
            //3.3 Solve the remaining problem.
            subsetsUtil(nums, i+1, current, res);

            //3.4 Unmake the choice
            current.remove(current.size()-1);
        }

         //4. Return
         return;
    }
}

Example problem 4: Combination sum

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>> ();
        combinationSumUtil(candidates, target, 
              0, new ArrayList<Integer> (), result);
    
        return result;
    }
    
    public void combinationSumUtil(int[] candidates, int target, 
                                   int index,
                                   List<Integer> current,
                                   List<List<Integer>> res ){
        
        /* Step 1: If the target has gone below zero, 
           nothing can be done.
           However, if the target is zero, then we found a
           the combination that adds up to the target, 
           so we put it into the list.
        */
        if(target < 0){
            return;    
        }
        if(target == 0){
            res.add(new ArrayList<>(current));
            return;
        }
        
        /* Step 2. Once we take the number, remaining numbers 
        are still available as choices, including the current number.
        */
        for(int i=index; i<candidates.length; i++){
            //3.1 : Is the choice safe
            if(target - candidates[i] >=0){
                
                //3.2 : Make the choice
                current.add(candidates[i]); 
                
                //3.3 Try to solve with the problem with above choice
                combinationSumUtil(candidates, 
                                   target-candidates[i], i,
                                   current, res);
                
                //3.4 Unmake the choice
                current.remove(current.size()-1);
            }
        }
        
        //Step 4: return
        return;
    }
}

Please share if there is something wrong or missing. If you are preparing for an interview and need help with preparations, please book a free session with us.