В контесте, где большинство задач решаются жадностью, нашел такую: "Постройте все сочетания из n элементов по k в таком порядке, чтобы два соседних сочетания отличались друг от друга не более чем одним элементом. Если существует несколько решений, выведите любое"

n и k от 1 до 15 TL 2 секунды ML 64 мб

Подразумеваются перестановка сочетаний, полученных в лексикографическом порядке, т.е. сочетание 2 1 система не засчитывает, в отличие от 1 2

Я не могу придумать параметр для сортировки, потому что количество различных элементов — относительная величина, и его не получается выражать через количество различных элементов с заданным сочетанием

Дополнительное условие для ветки рекурсии при генерации сочетаний, которое не нарушило бы их число/упорядоченность тоже не очевидно.

Как ее решать?