Recursive Backtracking

A Problem to Solve

• Find all combinations of 3 integers between 1 and 4 that sum to 5.

Brute Force Approach

• Enumerate all possible combinations

111 112 113 114   121 122 123 124   131 132 133 134   141 142 143 144
211 212 213 214   221 222 223 224   231 232 233 234   241 242 243 244
311 312 313 314   321 322 323 324   331 332 333 334   341 342 343 344
411 412 413 414   421 422 423 424   431 432 433 434   441 442 443 444

• Problem size: # digits raised to combination length
• 4 possible digits
• Combination length of 3
• Problem size = 4³ = 64
• Could generate each combination by using three loops

for i = 1 to 4:
  for j = 1 to 4:
    for k = 1 to 4:
      if sum(i, j, k) == 5:
        Found a combination
      else:
        Did not find a combination

• There is room for optimization, could stop if the first two values sum to 5.
• Provides for better real world performance, but doesn't change Big-O.
• Need a better approach

Backtracking Approach

• Use recursion to explore possible solutions
• Backtrack when recursion hits a dead end

find(int[] array, int i):
  if i == array.length:
    return
  sum = sum of array elements up to index i (exclusive)
  for guess from 1 to 4:
    array[i] = guess
    if i == array.length - 1 && sum + guess == 5:
      print array             //found one
      return                  //no more to be found at this i
    else if guess + sum >= 5:
      return                  //dead end
    else:
      find(array, i + 1)      //recurse
  return

Let's trace through the algorithm

Trace:
find(array=[?,?,?], i=0)
.sum = 0
.guess = 1: 
..find(array=[1,?,?], i=1)
...sum = 1
...guess = 1
....find(array=[1,1,?], i=2)
.....sum=2
.....guess=1
......find(array=[1,1,1], i=3) - return
.....guess=2
......find(array=[1,1,2], i=3) - return
.....guess=3
......find(array=[1,1,3], i=3) 
......print: [1,1,3]
......return
...guess=2
....find(array=[1,2,?], i=2)
.....sum=3
.....guess=1
......find(array=[1,2,1], i=3) - return
.....guess=2
......find(array=[1,2,2], i=3) - return
......print: [1,2,2]
......return
...guess=3
....(and so on...)

Backtracking

• Can think of solutions as forming a tree
• Each path from root to leaf is a complete solution
• Each step along that path is part of the solution (usually use a loop to iterate of each possible next step from the current one)
• If the path doesn't work out, we can about early (prunes the tree/search space)
• Even if that path is successful, we backtrack and explore other paths (if we want all solutions)
• For some problems stop at first solution, in other, find all solutions.

Rewriting the above example to be more versitile

• Solve for any size combination (array.length), and range of numbers (start, end), and any total

find(int start, int end, int total, int[] array, int i):
  if i == array.length:
    return
  sum = sum of array elements up to index i (exclusive)
  for guess from start to end:
    array[i] = guess
    if i == array.length - 1 && sum + guess == total:
      print array
      return
    else if guess + sum >= total:
      return
    else:
      find(start, end, total, array, i + 1)
  return

Finding a list of solutions

find(int start, int end, int total, int[] array, int i):
  list = new empty list
  if i == array.length:
    return list  //still empty
  sum = sum of array elements up to index i (exclusive)
  for guess from start to end:
    array[i] = guess
    if i == array.length - 1 && sum + guess == total:
      list.add(copy of array)
      return
    else if guess + sum >= total:
      return list  //might be empty
    else:
      sublist = find(start, end, total, array, i + 1)  //recurse
      list.addAll(sublist)
  return list //might be empty

A Solution in Java

import java.util.ArrayList;

public class ComboSumFinder {
  /** Prints all combos of 3 ints, each between 1 to 4, that add up to 5. */
  public static void main(String[] args) {
    ArrayList<int[]> combos = find(3, 1, 4, 5);
    for (int[] combo : combos) {
      System.out.println(java.util.Arrays.toString(combo));
    }
  }

  /**
   * Returns a list of all combos of the given length, formed of integers
   * between start and end (both inclusive), that add up to total.
   */
  public static ArrayList<int[]> find(int length, int start, int end, int total) {
    return find(start, end, total, new int[length], 0);
  }

  private static ArrayList<int[]> find(int start, int end, int total, 
                                             int[] array, int i) {
    ArrayList<int[]> list = new ArrayList<int[]>();
    if (i == array.length) {
      return list;
    }
    //sum of elements in array up to index i (exclusive)
    int sum = 0;
    for (int j = 0; j < i; j++) {
      sum += array[j];
    }

    //try each value for current array element from start to end
    for (int guess = start; guess <= end; guess++) {
      array[i] = guess;
      if (i == array.length - 1 && sum + guess == total) {
        list.add(java.util.Arrays.copyOf(array, array.length));
        break;
      }else if (guess + sum >= total) {
        return list;
      }else {
        ArrayList<int[]> sublist = find(start, end, total, array, i + 1);
        list.addAll(sublist);
      }
    }
    return list;
  }
}