What is an exhaustive search

Exhaustive search is a brute-force approach that allows exploring every possible combination from a set of choices. As you can see from the description when you faced a question about combinations, permutation. The first idea should be: Can I use an exhaustive search.

Here's the list of possible questions that an exhaustive search could solve:

• combinatorics
• Permutations. For instance, producing all permutations for a set of values

Let's try to solve a classic permutation problem. Given a number of digits, return all binary numbers that have exactly that many digits.

Example 1

Input:   2

Output:  ["00", "01", "10", "11"]

Example 2

Input:   1

Output:  ["0", "1"]

Before writing a code, let's try to see how we can generate all binary numbers with length 2.

The expected result is pretty obvious

00
01
10
11

Here's the idea of how we can generate all permutations.

• initially, we have an empty string
• we're adding one digit, and we have two choices 0 and 1
  • we selected 0
    • on this step, we have the digit of length one, but we need length 2 we're adding one more digit, and again we have two choices 0 and 1
      • we selected 0, and now we have 00
      • we selected 1, and now we have 01
  • we selected 1
    • on this step, we have the digit of length one, but we need length 2 we're adding one more digit, and again we have two choices 0 and 1
      • we selected 0, and now we have 10
      • we selected 0, and now we have 11

Here's the tree of calls

Often an exhaustive search is implemented recursively.

Code

      public List<string> GenerateBinaryNumbers(int digits)
      {
          if (digits == 0)
          {
              return new List<string>();
          }

          var result = new List<string>();
          GenerateBinaryNumbers(digits, string.Empty, result);
          return result;
      }

      private static void GenerateBinaryNumbers(int digits, string current, List<string> result)
      {
          if (digits == 0) // base case, no digits left
          {
              result.Add(current);
          }
          else
          {
              GenerateBinaryNumbers(digits - 1, current + "0", result); // we choose 0
              GenerateBinaryNumbers(digits - 1, current + "1", result); // we choose 1
          }
      }

As you can see, we produced all permutations. An exhaustive search it's an introduction to a backtracking algorithm.