Print all cominations of numbers in ascending order recursively (with length n between 1 and 9)

I want to print all number combinations that are in ascending order. The output should go like: 012, 013, 014, …, 789 for n = 3. I tried to solve it using recursion, however I’m having the StackOverflowError. So it means it never reaches the result. Here is my code so far:

public class Main {
  public static void main(String[] args) {

    int[] a = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0};
    print_combinations(a, 0, 3);
  }

  static void print_combinations(int[] a, int index, int n) {
    if (n > 0 && n < 10) {
      if (index == n - 1) {
        if (is_ascending(a, n)) {
          System.out.print(Arrays.toString(a));
          System.out.print(", ");
        }
        if (!has_ended(a, n)) {
          print_combinations(a, 0, n);
        }
      } else {
        while (a[index] <= 9 - n + index - 1) {
          print_combinations(a, index + 1, n);
          if (index < n - 1 && a[index] == 9 - n + index - 1) {
            a[index + 1] = 0;
          }
          a[index]++;
        }
      }
    }
  }

  static boolean has_ended(int[] a, int n) {
    int ctr = 0;
    while (ctr < n) {
      if (a[ctr] != 10 - n + ctr) {
        return false;
      } else {
        ctr++;
      }
    }
    return true;
  }

  static boolean is_ascending(int[] a, int n) {
    int ctr = 0;

    while (ctr < n - 1) {
      if (a[ctr] >= a[ctr + 1]) {
        return false;
      }
      ctr++;
    }
    return true;
  }
}```

Answer

There are these issues in your code:

• The base case is not when if (index == n - 1), because then you still need to populate a[index] will different digits. The base case is when if (index == n).

• Once the base case is treated, you should not make even deeper recursive calls, as you do with the if (!has_ended(a, n)) block. No, the principle of recursion is that you backtrack once you have reached the end of a search path, so you simply need to return. The caller will deal with other variations. This if block should be removed.

• The while loop ends too soon. Its condition should not be a[index] <= 9 - n + index - 1, but a[index] <= 9 - n + index + 1.

• The if condition inside that loop is testing the wrong array value, and comparing with the wrong limit. It should not be a[index] == 9 - n + index - 1, but a[index + 1] == 9 - n + index + 3.

• With Arrays.toString(a) you’ll get all 10 entries of a instead of the first n of them. You could do Arrays.toString(Arrays.copyOfRange(a, 0, n)).

With those fixes your code will work:

  static void print_combinations(int[] a, int index, int n) {
    if (n > 0 && n < 10) {
      if (index == n) {
        if (is_ascending(a, n)) {
          System.out.print(Arrays.toString(Arrays.copyOfRange(a, 0, n)));
          System.out.print(", ");
        }
      } else {
        while (a[index] <= 9 - n + index + 1) {
          print_combinations(a, index + 1, n);
          if (index < n - 1 && a[index + 1] == 9 - n + index + 3) {
            a[index + 1] = 0;
          }
          a[index]++;
        }
      }
    }
  }

There are more elegant ways to achieve the desired output, but at least this shows you where your code had issues.

Here is a version that does not allocate 10 array entries, but first defines n and then uses that for a dynamic length for the array. Also, the iteration over the different digits can be done with a for loop, and you can also add logic to not start each time at 0, but at one more than the digit at the left. This way you don’t need the check whether the array is ascending, as it is then guaranteed.

    public static void main(String[] args) {
        int n = 3;
        int[] a = new int[n];
        print_combinations(a, 0, n);
    }

    static void print_combinations(int[] a, int index, int n) {
        if (index == n) {
            System.out.print(Arrays.toString(a));
            System.out.print(", ");
        } else {
            int first = index > 0 ? a[index - 1] + 1 : 0;
            int last = 10 - n + index;
            for (int digit = first; digit <= last; digit++) {
                a[index] = digit;
                print_combinations(a, index + 1, n);
            }
        }
    }