[ivank]

P.S. В предыдущем посте я наврал. На самом деле при "лобовом подходе" перебирать надо даже SUM(k=1, n, C_n_k). Т.е. сумма всех цэ из эн по ка для всех ка от 1 до эн. Это ещё хуже.

Честно говоря, я склоняюсь к мысли, что эта сумма будет равна 2^n. Поскольку бинарных наборов длины n может быть всего 2^n. А каждый бинарный набор характеризует собой какую-то уникальную сумму (комбинацию чисел). Перебрать их, если делать втупую, надо все. В общем, чистая экспонента.

P.S. Только что проверил эту мысль на бумажке. Действительно, SUM(k=1, n, C_n_k) = 2^n.