Given an integer n, the task is to generate all n-digit numbers whose digits are in strictly increasing order from left to right. A digit sequence is considered strictly increasing if every digit is greater than the digit immediately before it.
For example, 123, 589, and 6789 are valid numbers because each digit is larger than the previous one. On the other hand, 122, 321, and 455 are invalid because they either contain repeated digits or do not follow increasing order.
Example
Consider the case where n = 2. The valid numbers are:
12, 13, 14, 15, 16, 17, 18, 19, 23, 24, ..., 79, 89
Notice that numbers such as 11, 21, or 98 are excluded because they violate the strictly increasing condition.
Key Observation
The most important observation is that once a digit is chosen, the next digit must always be greater than it. This naturally suggests a recursive or backtracking approach.
Instead of generating every possible n-digit number and checking whether it satisfies the condition, we can directly construct only the valid numbers. This significantly reduces unnecessary computations.
Recursive Construction
For example, suppose we want to generate all valid numbers of length 3.
We can start with digit 1:
This generates:
123, 124, 125, ..., 129
Similarly:
134, 135, ..., 189
The same process continues recursively until the required number of digits has been selected.
Information Maintained During Recursion
The recursion maintains three pieces of information:
Whenever the required length is reached, the generated number is added to the answer list.
Edge Cases
An important edge case occurs when n = 1. According to the problem statement, all single-digit numbers are considered strictly increasing. Therefore, the output should contain:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Another edge case occurs when n > 9. Since there are only nine non-zero digits available for forming a strictly increasing multi-digit number, it is impossible to create such a number with more than nine digits. Therefore, the answer is an empty list.
Dry Run
Let's understand the recursive generation using an example where n = 3.
Start with:
generate(3, 0, 1)
Choose digit 1:
generate(2, 1, 2)
Choose digit 2:
generate(1, 12, 3)
Choose digit 3:
generate(0, 123, 4)
Since no more digits are required, 123 is added to the result.
Backtracking then explores other possibilities:
124, 125, 126, ..., 129
After all combinations beginning with 12 are processed, recursion returns and explores numbers beginning with 13, then 14, and so on.
Why This Approach Works
This approach guarantees that:
Digits are always strictly increasing.
No duplicate numbers are generated.
Numbers appear in sorted order automatically.
Time Complexity
The time complexity is proportional to the number of valid combinations. Since we are choosing n digits from the set {1, 2, ..., 9}, the complexity is:
O(C(9, n))
where C(9, n) represents the number of possible combinations.
Space Complexity
The auxiliary space complexity is:
O(n)
because the maximum depth of the recursive call stack is equal to n.
Java Implementation
class Solution {
public static ArrayList<Integer> increasingNumbers(int n) {
ArrayList<Integer> ans = new ArrayList<>();
if (n == 1) {
for (int i = 0; i <= 9; i++) {
ans.add(i);
}
return ans;
}
if (n > 9) {
return ans;
}
generate(n, 0, 1, ans);
return ans;
}
private static void generate(int n, int num, int start,
ArrayList<Integer> ans) {
if (n == 0) {
ans.add(num);
return;
}
for (int digit = start; digit <= 9; digit++) {
generate(n - 1,
num * 10 + digit,
digit + 1,
ans);
}
}
}
This solution efficiently generates only valid numbers and avoids checking invalid combinations, making it an ideal approach for the problem.
Summary
This approach uses recursion with backtracking to directly construct only valid n-digit numbers whose digits are in strictly increasing order. By always selecting the next digit from a larger value than the previous one, it eliminates invalid combinations, guarantees sorted output without duplicates, and achieves a time complexity of O(C(9, n)) with an auxiliary space complexity of O(n).