Find all unique combinations of sum of a Number N

Question

Print all combinations of a number N, as a sum of positive integers?
They should be unique

Example

3 =
1 2

1 1 1

.

4=
3 1

2 2

1 1 2

1 1 1 1

I have made a solution for this using backtracking but the problem is that it is also giving duplicates for example for 3

I am getting

1 1 2

2 1 1

How to get unique combinations only?

Many many thanks in advance

Answer 1

When you create your back you will always start from the last number(for the first time you consider 1 as the last number)( basically you keep a sorted solution) this is how you always keep a unique solution.

#include <iostream>

const int N = 4;

int sol[N];
int sum = 0;
int nr_of_elements;

void back(int lastElement)
{
    if (sum == N)
    {
        for (int i = 0 ; i < nr_of_elements; i++)
            std :: cout << sol[i] << " ";
        std :: cout << "\n";
        return ;
    }
    for ( int i = lastElement ; i <= N - sum ; i++)
    {
        sum += i;
        sol[nr_of_elements++] = i;
        back(i);
        sum -= i;
        nr_of_elements--;
    }
}

int main ()
{
    back(1);
    return 0;
}