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.

Balanced partition problem

Balance partition problem

Given a set of integers, partition those integers into two parts where the difference between the two parts is minimum. This problem is known as balanced partition problem. For example, array A = {1,7,4,11}, two subsets can be: {1,11} and {7,4}, two have a difference of 1, which is the minimum difference we can get by splitting this array.

Mathematically, you have a set of n integers each in the range 0, . . . , K. Partition these integers into two subsets such that you minimize |S1 − S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.

Balance partition problem can be asked in many other ways, for instance,
given a list of 22 players and their strengths, divide those 22 players into two teams so that both teams are balanced.
Another version can be that you have “n” candy, each candy has a value associated with it. You want to distribute those candies between two kids as equally as possible.

No matter what version is asked, the approach remains the same.

Balance partition problem: thoughts

The brute force method will be to list down all the subsets of the given set and find the sum of each one of them. Then scan through the sum of all the subsets and find the two closest ones. For a set of n elements, there can be 2n subset. Therefore, the complexity of this brute force solution is already exponential.

Let me tweak balance partition problem a bit. We find if there are two subsets of the set of integers such that the difference between “sum” of these two subsets is zero.
Essentially, this is a special case of the original problem. If the difference between the sum of two subsets is zero that means the sum of both subsets should be exactly equal to half of the sum of all elements in the set.

So problem reduces to a smaller problem that is to find if there is a subset of integers which add up to half the sum of all integers in the set? This is the subset sum problem which we have already solved. 

How can we use information provided by subset set problem above?
Let’s say S is the sum of all the integers in the set. S/2 will be half of that sum. We have to find a subset with sum i such that S/2 -i is minimum.

Whether or not, there is a subset with sum i in the set is given by solving subset sum problem. For the sums, i, which are possible with subsets of the set, find the one which is the least distance from S/2. That will give us other subsets which is least greater than half of the sum of all elements of the set and that will be minimal difference possible between two subsets.

So,  expression would be as

min(S/2 - i) where T[n][i] = True and i>=0 and i<=S/2

Why we took i >=0 and i<S/2? Because, we want to be balanced, so i cannot be more than half of the total sum in any case.

Balanced partition problem: implementation

package com.company;

/**
 * Created by sangar on 25.11.18.
 */
public class BalancedPartition {
    public int findBalancePartition(int[] a){

        // Calculate sum of all the elements in set 
        int S = 0;
        for (int i=0; i<a.length; i++)
            S += a[i];

        boolean T[][] = new boolean[a.length + 1][S + 1];

        /* Initialize first column as true. 
            0 sum is possible with all elements. 
        */
        for (int i=0; i<=a.length; i++)
            T[i][0] = true;

        /*  Initialize top row, except dp[0][0], 
            as false. With 0 elements, no other 
            sum except 0 is possible
        */
        for (int i=1; i<=S; i++)
            T[0][i] = false;

        
        for (int i = 1; i <= a.length; i++) {
            for (int j = 1; j <= S; j++) {
                // If ith element is excluded 
                T[i][j] = T[i - 1][j];

                // If ith element is included 
                if (a[i - 1] <= j)
                    T[i][j] |= T[i - 1][j - a[i - 1]];
            }
        }

        // Initialize difference of two sums. 
        int diff = Integer.MAX_VALUE;

        for (int j = S/2; j >= 0; j--) {
            // Find the 
            if (T[a.length][j] == true)
            {
                diff = S - 2 * j;
                break;
            }
        }
        return diff;
    }
}

Once, we get the nearest sum, we can always backtrack the table and find elements of the subset itself. Actually, this problem is now reduced to 0/1 knapsack problem, where maximum value we can get is j from the set of integers.

Complexity to split set into two balanced partitions is O(n * S) with a space complexity of O(n * S), where S will be the max value array can have.

Please reach out if there is anything wrong or missing in the post. If you are preparing for an interview, please signup for free interview preparation kit.

0/1 knapsack problem using dynamic programming

0/1 Knapsack problem

0/1 Knapsack is a typical problem that is used to demonstrate the application of greedy algorithms as well as dynamic programming. There are cases when applying the greedy algorithm does not give an optimal solution. There are many flavors in which Knapsack problem can be asked.

1. A thief enters a museum and wants to steal artifacts from there. Every artifact has a weight and value associated with it. Thief carries a knapsack (bag) which can take only a specific weight. Problem is to find the combination of artifacts thief steals so that he gets maximum value and weight of all taken artifacts is less capacity of knapsack he has. A thief cannot take any artifact partially. Either he takes it or leaves it. Hence the problem is 0/1 knapsack.

2. We have N files each having a size say Si. We have a total storage capacity of W bytes. For each file to be stored re-computation cost is Vi. Problem is to store as many files on storage that combined size of all files is less than W and their re-computation value is maximum. We can either store or leave a file, we cannot store partial file. Hence this is a case of 0/1 knapsack problem.

0/1 knapsack problem : Line of thoughts

Brute force method would try all subsets of set of items, whose weight adds up to maximum capacity of knapsack and see which one gives maximum value. Complexity of brute force algorithm would be of exponential order as there will be 2n possible subsets for n items.

Can we do better? If we consider each item, there are two possibilities associated with it.
First, current item is included in optimal subset. Then we need to find out all the items in remaining N-1 items which can optimize the subproblem for weight W-wk. Value of this item is added to candidate maximum value.

Second, current item is not included in optimal subset. In that case, we need to find out items in remaining N-1 items which can optimize the the original problem. Value of current item is not added into candidate maximum value.

Inclusion depends on two conditions :

  1. Weight of the item is less than the total capacity of knapsack.
  2. Inclusion of item increases current max value with K-1 items with W-Wk weight.

Since every steps reduces the problem to a smaller problem in terms of items of weight, recursive solution would be our first refuge. To implement this problem, what are the base cases? First, we cannot add any items to knapsack capacity is zero i.e. W == 0. Second, no item can be taken if there are no items remaining, i.e. n == 0.

Recursive implementation of 0/1 knapsack problem

package com.company;
/**
	* Created by sangar on 19.8.18.
*/
public class KnapsackProblem {
	static int knapSack(int W, int[] weights, int[] val, int n) {
		/*
			If there is no item or weight that can be carried is
			zero, return zero
		*/
		if (n < 0 || W == 0)
			return 0;

		/* 
			If weight of the nth item is more than Knapsack 
			capacity W,then this item cannot be included
			in the optimal solution
		*/
		if (weights[n] > W)
			return knapSack(W, weights, val, n - 1);

		/* Consider two cases, including item and excluding item.*/
		else return Integer.max(
			(val[n]
				+ knapSack(W - weights[n], weights, val, n - 1)),
			(knapSack(W, weights, val, n - 1))
		);
	}

	public static void main(String args[]) {
		int[] val = {60, 100, 120};
		int[] wt = {10, 20, 30};
		int W = 50;
	
		int n = val.length;
		System.out.println(knapSack(W, wt, val, n - 1));
	}
}

If we look at the execution trace of the function, it looks like this.

0/1 knapsack problem

There are seven problems to be solved at the leaf level. For N = 3, there are 7 problems to be solved before we start optimizing for the max value. For N, in general, it will take 2N subproblems to be solved. Hence, complexity of recursive implementation is O(2N).

If we take another example, it will become evident that there are some subproblems that are solved again and again. Overlapping subproblems is one of the criteria, we should be thinking about dynamic programming. Also, notice that optimal solution to a smaller problem leads to the optimal solution to a bigger problem, which is the second condition for DP. This problem satisfy both these conditions, hence let’s design DP solution for it.

0/1 knapsack problem : Dynamic programming approach

We define two dimensional array V[N,W] where N is number of items and W is capacity. For 1<= i <= n and 0<=w<=W, V[i,w] represents the optimal solution for items I1, I2, ..In with maximum weight of w. If we can compute all the entries of this array, then the array entry V[N,W] is the solution to our problem

For i =0 and w=0, all values will be zero. So, first column and first row will be filled with all zero values.
Recursively, we can fill the table bottom up as follows.

V[i, w ] = max (V[i-1, w], V[i-1, w-w[i]) + V[i] )
V[0, w ] = 0; there are no items
V[i, 0 ] = 0; no items can be picked.
package com.company;

/**
	* Created by sangar on 19.8.18.
*/
public class KnapsackProblem {
	public static int knapsackDP(int W, int[] weights, int[] val, int n) {
		int[][] V = new int[n+1][W + 1];
		for(int i = 1 ; i < V[0].length; i++){
			/*
				If weight of item is less than current value
				we can achieve minimum value V[i] with 1..i items
			*/
			if(weights[0] <= i){
				V[0][i] = val[0];
			}else{
				V[0][i] = 0;
			}
		}

		//Loop for all items
		for (int i = 1; i < V.length; i++) {
			for (int j = 1; j < V[i].length; j++) {
				/*if a weight is more than the allowed weight, 
				that weight cannot be picked. */
				if(weights[i] > j){
					V[i][j] = V[i-1][j];
				}else{
					V[i][j] = Math.max(V[i-1][j], 
							val[i] + V[i-1][j-weights[i]]);
				}
			}
		}
		return V[V.length-1][W];
	}

	public static void main(String args[]) {
		int[] val = {60, 100, 120};
		int[] wt = {10, 20, 30};
		int W = 50;

		int n = val.length;
		System.out.println(knapsackDP(W, wt, val, n - 1));
	}
}

One similar problem which can be solved with the same approach is the minimum number of coins to be used to get a change of a particular amount.

Complexity of the dynamic programming implementation of knapsack problem is O(N *W). Space complexity is again O(N*W). It is thumb rule that we trade space for time in dynamic programming.

Please share if there is something is wrong or missing. If you want to contribute to website, please reach out to us at communications@algorithmsandme.com