Generate n-Length K-ary String

Table of contents

1. Problem
2. Backtracking

---

Problem

Generate all possible n-length k-ary strings.

K-ary string is a string that only contains characters from the set $\{0, 1, \ldots, k-1\}$.

---

Backtracking

1. Create an array arr of length n, initialized with all zeros.
2. Have a helper function that wil print the array arr as a single string.
3. In the recursion:

  void generate(int[] arr, int n, int k) {
    if (n < 1) {
      printArray(arr);
    } else {
      for (int i = 0; i < k; i++) {
        arr[n - 1] = i;
        generate(arr, n - 1, k);
      }
    }
  }

The idea is to fix a single character at a time, and recursively generate all possible strings with the fixed character.

Once all possibilities with the fixed character are exhausted, we move on to experiment with another character.

The recurrence relation is

\[T(n) = k T(n - 1) + O(n)\]

which is $O(k^n) \cdot O(n)$.

The $O(n)$ comes from naively printing the array as a string.