Lucky tickets: hints, no solution
Easy · Backtracking
A festival prints raffle tickets whose codes are strings of exactly n digits, where every digit is 1, 2 or 3; the digit 0 is never used. A ticket is lucky when its digits add up to a given total.
Return every lucky code as a list of strings in ascending order, comparing codes the way words are compared in a dictionary, so that 112 comes before 121. Each code appears once. If no code has the requested digit sum, return an empty list.
Examples
- Input
- n = 3, total = 6
- Output
- ["123", "132", "213", "222", "231", "312", "321"]
- Note
- Any arrangement of 1, 2, 3 works, and so does 2, 2, 2.
- Input
- n = 2, total = 7
- Output
- []
- Note
- Two digits from 1 to 3 add up to at most 6.
Constraints
- 1 <= n <= 30
- 0 <= total <= 90
- Each digit of a code is 1, 2 or 3
- The result has at most 300 codes
Hint 1: a nudge
When you have already written some digits, what do you still need from the remaining positions, and how large or small can that be?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.