找到数字N之和的所有唯一组合

Question

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

例

3 =
1 2

1 1 1

.

4=
3 1

2 2

1 1 2

1 1 1 1

我已经使用回溯为此做了一个解决方案,但问题是它也提供重复,例如3

我正进入(状态

1 1 2

2 1 1

如何才能获得独特的组合？

许多人提前感谢

Answer 1

当您创建背部时,您将始终从最后一个数字开始(第一次将1视为最后一个数字)(基本上您保留一个已排序的解决方案)这就是您始终保持唯一解决方案的方式.

#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;
}