Разбиение чисел на слагаемые

[ololo-schoolboy]

Всех с праздником, недавно написал не большую программу, для разбивания числа, на слагаемые, как сделать чтоб не было комбинаций с одинаковыми слагаемыми, стоящими в разном порядке, можно конечно создать массив и хранить в нем все комбинации которые уже были, но может есть другой вариант?

/*m число, n номер слагаемого, sum сумма уже подобранных слагаемых, parts массив где хранятся слагаемые, end индекс  последнего элемента*/
void IntToParts(int m, int n, int sum, int* parts, int end)
{
	if(n<end)
	{
/*end-n число оставшихся слагаемых слагаемое - натуральное число*/
		for(int i=1; i<=m-(end-n+sum); ++i)
		{
			parts[n]=i;
			IntToParts(m, n+1, sum+i, parts, end);
		}
	}
	else
	{
/*если элемент последний пихаем в него все что осталось*/
			parts[n]=m-sum;
			std::cout<<parts[0];
			for(int j=1; j<=end; ++j)
				std::cout<<'+'<<parts[j];
			std::cout<<'='<<m<<std::endl;
	}
}

[Ru_DoLF]

но может есть другой вариант?

есть

#include <iostream>

using namespace std;

int main()
{

	int n;

	cin >> n;

	for (int i = 0; i <= n/2; ++i)
		cout << i << " + " << n - i << endl;

	return 0;

}

[ololo-schoolboy]

ну это я и так знаю, тока не факт что end+1==2

вот думаю что делать с массивом для начала узнать какого размера он будет мб есть формулы какие-то?

[Obey-Kun]

Используй std::vector же

[ololo-schoolboy]

Используй std::vector же

не принципиально.

написал функцию для добавления элемента в массив, ни как не могу отладить, выдает полный бред

/*combinations массив с комбинациями, combCount индекс свободного элемента, nowCombination отсортированный от меньшего к большему массив, size размер массива nowCombination и число колонок в массиве combinations*/
void addCombination(int** combinations, int combCount, int* nowCombination, int size)
{
	memcpy(combinations[combCount], nowCombination, sizeof(int)*size);
	int top = 0;//верхняя граница
	int lower = combCount-1;//нижняя граница
	for(int i=0, j; i<size; ++i)//i столбец по которому сортирую
	{
			int* x = new int[size];
			memcpy(x, combinations[lower+1], sizeof(int)*size);
			/*сортировка вставками*/
			for (j=lower; j>=top && combinations[j][i] > x[i]; j--)
				memcpy(combinations[j+1], combinations[j], sizeof(int)*size);
			memcpy(combinations[j+1], x, sizeof(int)*size);
			delete[] x;
			if(j>=0 && combinations[j][i]==combinations[j+1][i])/*если перед тем что мы вставили что-нибудь есть и это что-то равно тому что мы вставили в i-том столбце*/
			{
				lower = j;
				top = j;
				while(j>=0 && combinations[j][i]==combinations[lower+1][i]) /*самая верхняя строка где i-тый столбец равен i-тому столбцу того что мы вставляем*/
					top =j--;
			}
			else /*если нет элементов с идентичным значением в i-том столбце сортировать по другим столбцам не с чем*/
				break;
	}
}

заранее из извиняюсь за не читабельность, я в курсе что есть всякая хрень в коде типа new int[size] можно было каждый раз не выделять и т.д. потом это подправлю... не понятно почему он все перепутывает

[ololo-schoolboy]

сори за тупизну насчет размера разобрался, осталось отсортировать

[Obey-Kun]

сортируй с помощью std::sort

[ololo-schoolboy]

он не подойдет у меня все уже отсортировано нужно только вставить еще одну комбинацию в нужное место

[Obey-Kun]

блин, не изобретай велосипед, есть std::list/std::vector, там есть insert.

[ololo-schoolboy]

insert вставит в конец, а я хочу вставить так чтоб сортировка не нарушалась