Digit Orderings Under a Limit
Problem
Given a list of distinct digits and a limit, return every number that uses each digit exactly once, in some order, and is at most the limit, in increasing order. A number may not start with 0 unless it is the single digit 0. There are at most 8 digits.
Examples
Input: digits = [3, 1, 2], limit = 300
Output: [123, 132, 213, 231]
Why: 312 and 321 are over the limit, and trying digits in increasing order yields the numbers already sortedInput: digits = [0, 2, 1], limit = 999
Output: [102, 120, 201, 210]
Why: orderings that start with 0 are skipped, because 012 is really a two-digit numberInput: digits = [5], limit = 4
Output: []
Why: edge case, the only ordering is already over the limitHints
0 / 3
Build the number one digit at a time, marking each digit as used while it sits in the current prefix and unmarking it when you back out.
Sort the digits first. Then the numbers come out in increasing order without a final sort, because every prefix is tried from its smallest next digit.
Prune: a prefix followed by r more digits is at least prefix × 10 to the r. If that already exceeds the limit, every larger next digit will too, so stop the loop.
Solution
This is the permutation template with a used array: pick an unused digit, recurse, then release it. Sorting the digits first makes the search visit prefixes in increasing order, so the results are sorted for free. The limit gives a cheap prune: filling the rest with anything at all makes the number at least the prefix shifted left by the remaining positions, so once that bound passes the limit, this digit and every larger one can be skipped with a break. The leading-zero rule is one condition on the first position. In the worst case all n! orderings are built, so time is O(n × n!) and space is O(n) for the recursion, plus the output.
def orderings_up_to(digits, limit):
digits = sorted(digits) # increasing digits give sorted output
used = [False] * len(digits)
out = []
def place(value, length):
if length == len(digits):
out.append(value)
return
for i, d in enumerate(digits):
if used[i] or (length == 0 and d == 0 and len(digits) > 1):
continue # used already, or a leading zero
nxt = value * 10 + d
if nxt * 10 ** (len(digits) - length - 1) > limit:
break # the smallest completion is too big
used[i] = True
place(nxt, length + 1)
used[i] = False # back out
place(0, 0)
return out
print(orderings_up_to([3, 1, 2], 300)) # -> [123, 132, 213, 231]
print(orderings_up_to([0, 2, 1], 999)) # -> [102, 120, 201, 210]
print(orderings_up_to([5], 4)) # -> []Stuck on the idea rather than the code? Permutations covers it.