Как перебрать все суммы массива?

Question

[ColdHandGuy]

Требуется перебрать всевозможные суммы массива. Например: при int A[] = {1, 2, 3} выводит 0,1,2,3,3,4,5,6 Массив при этом может быть любой длины N. Как можно реализовать этот алгоритм? Понимаю, что функция должна быть скорее всего рекурсивной, но вот реализовать никак не соображаю как.

Comments

[edward_freedom]

сделай хоть что то и приди сюда с наработками

Answer 1

[Wataru]

Можно не рекурсивно.

Перебирите все битовые маски (числа) от 0 до 2^n -1 (mask = 0; mask < (1 << n); ++mask).

А внутри при подсчете суммы пройдитесь по всем позициям массива и, если i-ый бит установлен, прибавляйте текущее число. Проверить, что бит установлен можно сделав побитовое и (&) c 1 << i.

Если хотите рукурсивно, то пусть ваша функция принимает текущую позицию и сумму. Если позиция равна n - выводите сумму. Иначе запускайтесь рекурсивно от следующей позиции два раза - с текущей суммой без изменения, и с суммой увеличенной на текущее число.

Answer 2

[ColdHandGuy]

Действительно, битовые операции я и не думал использовать, спасибо. Прикреплю простенький пример для следующих искателей:

#include <iostream>

using namespace std;

int main()
{
	int const n = 3;
	int intArray[n];
	int sum;

	for (int i = 0; i < n; i++)
	{
		cin >> intArray[i];
	}

	for (int mask = 0; mask < (1 << n); ++mask)
	{
		sum = 0;
		for (int i = 0; i < n; i++)
		{
			if (mask & (1 << i))
			{
				sum = sum + intArray[i];
			}
		}
		cout << sum <<" ";
	}

	return 0;
}