Для заданного набора S найдите все максимальные подмножества, сумма которых <= k

Это вопрос из интервью на 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} опускаются. .
• Для ее решения можно использовать лексикографическое упорядочение.

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