Combinations

Средняя№77сочетания

Даны два числа, n и k. Нужно вернуть все способы выбрать k разных чисел от 1 до n, причём порядок не важен: [1, 2] и [2, 1] — один и тот же выбор. Наш пример: n = 4, k = 3 даёт 4 выбора: [1, 2, 3], [1, 2, 4], [1, 3, 4] и [2, 3, 4].

77 CombinationsРазбор · 1×

Пример: 3 числа из чисел от 1 до 4. Смотрите на корень: x останавливается на 2, потому что с 3 остались бы только 3 и 4 — два числа на три места.

[ ]11,21,2,31,2,41,31,3,422,32,3,4числа1234путь—результаты—
ещё не былипо пути сюдаэтот шагсохранённое сочетаниене пробуем: после него не хватит чиселзакончено, или до start: недоступно

Ищем все способы выбрать 3 числа из чисел от 1 до 4

01/47
сначала · назад · пуск · шаг
Скорость
1function combine(n, k):
2 path = []
3 results = []
4 choose(1)
5 return results
6
7function choose(start):
8 if len(path) == k:
9 add copy of path to results
10 return
11 need = k - len(path)
12 for x from start to n - need + 1: // leave room
13 path.add(x)
14 choose(x + 1)
15 path.removeLast()
состояние
start
–
need
–
x
–
path
–
results
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждый вызов берёт только числа после последнего в пути, поэтому каждое сочетание собирается один раз, по возрастанию, и [2, 1] не повторяет [1, 2].
  2. Путь сохраняется ровно тогда, когда в нём k чисел; потом последнее число убирается, и цикл ставит на его место следующее.
  3. Если осталось need мест, то начало больше n − need + 1 оставляет меньше need чисел, и ветка не может закончиться: граница цикла пропускает её, не спускаясь.

Сложность

Время O(k × C(n, k)): граница цикла даёт каждому начатому пути дойти до k чисел, поэтому вызовов не больше k на ответ, и каждый ответ — копия k чисел. Память O(k) помимо ответа: путь и стек вызовов.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.