Partiții număr natural

Cerință:

Să se afișeze toate partițiile unui număr natural nenul n. Printr-o partiție a lui n se înțelege o descompunere a lui n ca sumă de numere naturale nenule.
Vom reprezenta o soluție printr-un vector x de lungime maximă n, având lungimea efectiv folosită k. Firește, condițiile interne ale tabloului x sunt ca suma celor k componente să fie n, deci acest vector reprezintă, de fapt, descompunerea lui n ca sumă de k numere.

Implementare:

Cod Sursa C++

// PartitiiMultimiCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int x[100], n;
 
void afisare(int n)
{
	int i;
	for (i = 1; i <= n; i++)
		cout << x[i] << "+";
	cout << "\b ";
	cout << endl;
}
 
int verif(int i)
{
	if (i>1 && x[i]<x[i - 1])
		return 0;
	return 1;
}
 
void back(int i, int s)
{
	int j;
	for (j = 1; j <= s; j++)
	{
		x[i] = j;
		if (x[i] == s)
			afisare(i);
		else back(i + 1, s - x[i]);
	}
}
 
int main()
{
	cout<<"Dati numarul ce se va descopmpune: " << endl;
	cin >> n;
	back(1, n);
	system("pause");
}

Rezultat