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
I have made a solution for this using backtracking but the problem is that it is also giving duplicates for example for 3
我收到
1 1 2
2 1 1
如何只得到独特的组合?
How to get unique combinations only?
许多许多在此先感谢
当你创建你的背部,你将总是从最后一个数字开始(在第一次你认为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;
}