Это вопрос интервью на Facebook, с которым я столкнулся на онлайн-портале.

Для заданного множества S найти все максимальные подмножества, сумма которых <= k. Например, если S = {1, 2, 3, 4, 5} и k = 7, вывод будет: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3 , 4}

подсказки:

Вывод не содержит никакого набора, который является подмножеством другого.Если X = {1, 2, 3} является одним из решений, то все подмножества X {1} {2} {3} {1, 2} {1, 3} {2, 3} опущены.Для ее решения может использоваться лексикографическое упорядочение.

Есть идеи, как это можно решить?