Combination Sum III
Real-world version: Notch Sets for a Key BlankThe statement here is our own: the same inputs, outputs and technique.
A locksmith cuts notches into a key blank. A notch is cut to one of the nine standard depths 1 through 9, and a blank may not carry two notches of the same depth. A cutting plan is a set of count notch depths whose depths add up to total.
Return every cutting plan. Each plan must list its depths in increasing order, and the plans themselves must be ordered so that, comparing two plans depth by depth from the shallowest, the one with the smaller depth at the first place they differ comes first. Return an empty list when no plan exists.
Examples
Example 1
- Input
- count = 2, total = 7
- Output
- [[1, 6], [2, 5], [3, 4]]
Each listed plan cuts two notches of different depths that add up to 7, and the plans are ordered by their shallowest notch.
Example 2
- Input
- count = 4, total = 30
- Output
- [[6, 7, 8, 9]]
Every plan shown holds four different depths adding up to 30, for example 6 plus 7 plus 8 plus 9.
Example 3
- Input
- count = 3, total = 60
- Output
- []
Three different depths reach at most 9 plus 8 plus 7, which is 24, so no plan reaches 60 and the answer is the empty list.
Constraints
- 2 <= count <= 9
- 1 <= total <= 60
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def notch_sets(count: int, total: int) -> list[list[int]]:public List<List<Integer>> notchSets(int count, int total)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's