Skip to content
Advertisement

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:

JavaScript

Advertisement

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:

JavaScript

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.

JavaScript
User contributions licensed under: CC BY-SA
6 People found this is helpful
Advertisement