Exhaustive search and backtracking

• Often implemented recursively
• Sometimes called recursive enumeration

• producing all permutations of a set of values
• enumerating all possible names, passwords, etc.
• solving puzzles/games, e.g., Sudoku, Chess.

• Example: when enumerating all 5-letter strings, each of the 5 letters is a decision, and each of those decisios has 26 possible choices.

General pseudo-code algorithm for exhaustive search:

Choosing
1. We generally iterate over "decisions". What are we iterating over here? The iteration will be done by recursion.
2. What are the "choices" for each decision? Do we need a for loop?

Exploring
3. How can we "represent" that choice? How should we "modify the parameters"?
   a) Do we need to use a "wrapper" due to extra parameters?

Un-choosing
4. How do we "un-modify" the parameters from step 3? Do we need to explicitly un-modify or are they copied? Are the un-modified at the same level as they were modified?

Base case
5. What should we do in the "base case" when we are out of decisions?

Example? printAllBinary

printAllBinary(2):
00
01
10
11

printAllBinary(3):
000
001
010
011
100
101
110
111

1. We are iterating over characters in the binary string
2. Choices: 0 or 1
3. Representation? Build up a string that we will eventually print. Add the 0 or 1 to it. String tracks our previous choices.
4. Unchoosing? If new strings for ever call, do not need to un-choose (they are getting copied)
5. Base case? print the accumulated string

void
printAllBinaryHelper(int digits, string soFar)
{
  if (digits == 0) {
    cout << soFar << endl;
  } else {
    printAllBinaryHelper(digits - 1, soFar + "0");
    printAllBinaryHelper(digits - 1, soFar + "1");
  }
}

void printAllBinary(int numDigits)
{
  printAllBinaryHelper(numDigits, "");
}

Notice that un-choosing was not required because we are copying the string representation (due to pass-by-value) on every recursive call. If we instead use pass-by-reference, the code would look something like the following (and it includes un-choosing logic):

void
printAllBinaryHelper(int digits, string &soFar)
{
  if (digits == 0) {
    cout << soFar << endl;
  } else {
    soFar = soFar + "0";
    printAllBinaryHelper(digits - 1, soFar);
    soFar = soFar.substr(0, soFar.length() - 1);
    soFar = soFar + "1";
    printAllBinaryHelper(digits - 1, soFar);
    soFar = soFar.substr(0, soFar.length() - 1);
  }
}

void printAllBinary(int numDigits)
{
  string soFar = "";
  printAllBinaryHelper(numDigits, soFar);
}

Another example: printAllDecimal(int numDigits): need a loop here.

void
printAllDecimalHelper(int digits, string soFar)
{
  if (digits == 0) {
    cout << soFar << endl;
  } else {
    for (int i = 0; i < 10; i++) {
      printAllDecimalHelper(digits - 1, soFar + integerToString(i));
    }
  }
}

void printAllDecimal(int numDigits)
{
  printAllDecimalHelper(numDigits, "");
}