All problems

Run-Together Bibs

Medium · backtracking

After a fun run, a volunteer typed the bib numbers of the finishers into one long string of digits, digits, and forgot to put spaces between them. Nobody can now tell where one number ends and the next begins.

What is known: every bib number is a whole number from 1 to limit, written with no leading zeros (so 07 is not a bib number, and neither is 0), and the numbers were typed in finishing order. Nobody crosses the line twice, so no bib number appears more than once.

Return every way the string could have been written. Each way is the list of bib numbers you get by cutting digits into consecutive pieces so that all the rules above hold. Every digit must belong to exactly one piece, and the pieces must keep their order. Each way must appear exactly once, and the ways may be returned in any order. If there is no way, return an empty list.

Examples

Example 1

Input: digits = "1212", limit = 50

Output: [[12, 1, 2], [1, 21, 2], [1, 2, 12]]

Reading it as 1, 2, 1, 2 repeats numbers, and so does 12, 12. Three readings are left, such as 1, 21, 2.

Example 2

Input: digits = "1002", limit = 1000

Output: [[100, 2]]

A piece cannot start with 0, so the zeros stay inside the number 100 and the 2 is the next bib. Reading it as the single number 1002 is above the limit.

Example 3

Input: digits = "908", limit = 1000

Output: [[908], [90, 8]]

Cutting after the 9 would leave a piece starting with 0, so only 90 then 8, and 908 on its own, remain.

Constraints