Backtracking

Two recursive algorithms

• Exhaustive Search
• Backtracking

These are brute-force algorithms

Used for problems that have a small and well-defined search space, where it is feasible to check all possible solutions

Backtracking

Main idea: find every solution incrementally by trying different options, then abandoning them if they are not suitable

In other words: exhaustive search + conditions for suitable solution

Application: Dice roll sum

Write a Java application that given two integers representing 1) how many dice to roll, and 2) the target sum of all dice values, it outputs all combinations of dice values that add up to the target sum.

Example call:

targetSum = 7;
getValidCombinations(2);

Output:

[1, 6]
[2, 5]
[3, 4]
[4, 3]
[5, 2]
[6, 1]

Solution 1

import java.util.ArrayList;

public class DiceBacktracking {
    
    public static int sumAll(ArrayList<Integer> values) {
        int sum = 0;
        for (int v : values) sum += v;
        return sum;
    }
    
    public static void getValidCombinations(int count,
                                            ArrayList<ArrayList<Integer>> result,
                                            ArrayList<Integer> values) {
        if (count == 0) {
            if (sumAll(values) == targetSum) {
                ArrayList<Integer> valuesToAdd = new ArrayList<Integer>(values);
                result.add(valuesToAdd);
            }
        }
        else {
            for (int v = 1; v <= 6; v++) {
                values.add(v); 
                getValidCombinations(count - 1, result, values);
                values.remove(values.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
      ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
      ArrayList<Integer> values = new ArrayList<Integer>();
      
      int targetSum = 7;
        getValidCombinations(2, result, values);
        
        for (ArrayList<Integer> v : result) System.out.println(v);
        
    }
}

Optimizations (Pruning)

We can preemptively stop, or prune, branches in the decision tree that cannot lead to a valid solution:

• current sum is already too high (rolling all 1s in the remaining dice will cause it to go over target sum)
• current sum is already too low (rolling all 6s in the remaining dice will cause it to be under target sum)

Solution 2

import java.util.ArrayList;


public class DiceBacktracking {
    
    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> ();
        ArrayList<Integer> values = new ArrayList<Integer>();
        int targetSum = 5;
        getValidCombinations(2, 0, result, values, targetSum);
        for (ArrayList<Integer> v : result) System.out.println(v);
    }
    
  public static void getValidCombinations(int count, int currentSum,
                                          ArrayList<ArrayList<Integer>> result,
                                          ArrayList<Integer> values,
                                          int targetSum) {
        if (count == 0) {
            if (currentSum == targetSum) {
                ArrayList<Integer> valuesToAdd = new ArrayList<Integer>(values);
                result.add(valuesToAdd);
            }
        } else if (currentSum + 1 * count > targetSum ||
                   currentSum + 6 * count < targetSum) {
                      return;
        } else {
            for (int v = 1; v <= 6; v++) {
                values.add(v);
                getValidCombinations(count-1, currentSum+v, result, values, targetSum);
                values.remove(values.size()-1);
            }
        }
    }
}