все возможные суммы

Ищи: Алгоритм генерации всех подмножеств конечного множества

= сумма (числа сочетаний их 4 по i ), где i от 2 до 4 = = 4!/(2!*2!) + 4!/(1!*3!)+4!/(0!*4!) = 6+ 4 +1 = 11

Комбинаторика, мать ее за ногу!

по правилу 'от перестановки мест 2-х слогаемых сумма не меняется' [1]

в случае когда слагаемы четыре можно переставить любые два слогаемые и при этом сумма не поменяется .. тоесть всего разных сумм C(4,2)=6 - перебирая все перестановки получаем все 6ть сумм ..

тоже самое и для случая когда в сумме 3 слагаемых - C(3,2)=3

для случая когда 2 - слагаемых сумма не меняется ..

Shell сойдет? :-)

bash-2.05$ more generator
add() {
local first=$1
echo $1
while [ $# -gt 1 ]
do
shift
add $first+$*
done
}

generate() {
while [ $# -gt 0 ]
do
add $*
shift
done
}

generate 1 3 8 11

bash-2.05$ ./generator
1
1+3
1+3+8
1+3+8+11
1+3+11
1+8
1+8+11
1+11
3
3+8
3+8+11
3+11
8
8+11
11

Итого 15 вариантов, как и ожидалось :-)

>= сумма (числа сочетаний их 4 по i ), где i от 2 до 4 = = 4!/(2!*2!) + 4!/(1!*3!)+4!/(0!*4!) = 6+ 4 +1 = 11

на самом деле можно предложить более общую формулу, которая учитывает, что в последовательности могут быть одинаковые числа (таким образом получим мультимножество):

{(a1, n1), (a2, n2), ... , (am, nm)}

где ai - число из последовательности ni - количество раз, которое оно встречается в последовательности пусть N = сумма(ni), где i от 1 до m

тогда формула будет такой

= сумма ((числа сочетаний из N по i)/(n1!*n2!*...*nm!)) , i от 2 до N

а если оптимизить, то

= (сумма (числа сочетаний из N по i), i от 2 до N)/(n1!*n2!*...*nm!)

выше был мой температурный бред. :) это все неверно. так как насчет задачи, где числа в последовательности могут повторяться?

простой и эффективный алгоритм:
если есть последовательность a1, a2, ... ,an, (значения могут повторяться) -- составляешь многочлен:
(1+x^a1)(1+x^a2)...(1+x^an)
раскрываешь скобки;
те степени x, при которых в результате стоит ненулевой коэффициент, и есть все возможные суммы.

при вычислениях можно ограничиться многочленами степени a1+...+an
следовательно сложность алгоритма получается порядка n*(a1+..+an)

в отличие от перебора всех подмножеств, при котором сложность экспоненциальна по n