Сумма комбинаций III

Найдите все допустимые комбинации из k чисел, которые в сумме дают n, при соблюдении следующих условий:

• Используются только числа от 1 до 9.
• Каждое число можно использовать не более одного раза.

Верните список всех возможных валидных комбинаций.

Список не должен содержать одинаковых комбинаций, и порядок их возврата не важен.

Пример 1:

Ввод: k = 3, n = 7
Вывод: [[1,2,4]]

Пояснение:

1 + 2 + 4 = 7

Других подходящих комбинаций нет.

Пример 2:

Ввод: k = 3, n = 9
Вывод: [[1,2,6],[1,3,5],[2,3,4]]

Пояснение:

1 + 2 + 6 = 9

1 + 3 + 5 = 9

2 + 3 + 4 = 9

Других подходящих комбинаций нет.

Пример 3:

Ввод: k = 4, n = 1
Вывод: []

Пояснение:

Чтобы выбрать 4 разных числа в диапазоне [1,9], минимальная сумма будет 1 + 2 + 3 + 4 = 10.

Так как 10 > 1, подходящих комбинаций не существует.

Ограничения:

• 2 ≤ k ≤ 9
• 1 ≤ n ≤ 60