Backtracking - descompunere suma - toate combinatiile

//Descompunere suma - toate combinatiile

# include <iostream.h>;
# include <conio.h>;

# define MAX 10

int sum,cont;
int sol[MAX];

void final(int n)
{
int i;
for(i=0;i<n;i++)
 cout<<sol[i]<<" ";
cout<<"\n";
cont++;
}

int verif(int j, int s)
{
if(j+s<=sum) return 1;
else return 0;
}

void back(int k, int s)
{
int j;

if(s==sum) final(k);
else
 for(j=1;j<sum;j++)
  if(verif(j,k))
   {
    sol[k]=j;
    back(k+1,s+j);
   }
}

void main(void)
{
clrscr();
cout<<"Intr suma: ";
 cin>>sum;

back(0,0);
cout<<"Nr. sol= "<<cont;
getche();
}
// Descompunere suma - combinatii distincte
// Descompunere suma - combinatii distincte si numere distincte
// Descompunere suma - combinatii cu nr prime (test)
// Descompunere suma - combinatii cu nr prime (test)

// Descompunerea unei table de sah in dreptunghiuri disjuncte diferite
//2 cate 2, care au un nr. de patrate albe = nr de patrate negre
//(N^2 in suma de numere pare)

// Plata unei sume in monezi