All problems

Combination Sum III

Medium · backtracking

A box holds one ticket for each whole number from 1 to n. You pick exactly k different tickets so that the numbers on them add up to target.

Return every set of tickets that works. Write each set in ascending order, and list every possible set exactly once. The sets may be returned in any order. If no set works, return an empty list.

Examples

Example 1

Input: n = 7, k = 3, target = 12

Output: [[1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5]]

Each set has three different numbers from 1 to 7 and adds up to 12.

Example 2

Input: n = 9, k = 2, target = 3

Output: [[1, 2]]

Only 1 and 2 are two different tickets that add up to 3.

Example 3

Input: n = 5, k = 4, target = 2

Output: []

Four different tickets add up to at least 1 + 2 + 3 + 4 = 10.

Constraints