Генерация подмножеств мультимножества в порядке возрастания сумм элементов подмножества
Я пытаюсь придумать алгоритм, в котором вы можете генерировать комбинации из набора в таком порядке, чтобы их суммы были в порядке возрастания. Этот набор должен быть мультимножеством, т.е. допускается повторение.
Например, у вас есть набор S = {1,2,2,3,4,5,5}
Таким образом, вместо генерации всех комбинаций на основе количества элементов (скажем, начните с 1 и 2 элементов и, наконец, всех 7), я хочу вычислить их в следующем порядке:
{1}, {2}, {2}, {1,2}, {1,2}, {3}, {1,3}, {2,2}, {4}.............. {1,2,2,3,4,5,5}
Почему этот порядок: хорошо взяв сумму этих подмножеств, мы можем увидеть:
{1}, {2}, {2}, {3}, {3}, {3}, {4}, {4}, {4}.............. { 22}
Вы знаете какой-нибудь алгоритм, который может сделать это эффективно???