本文介绍了找到的数量无金额的所有独特的组合的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
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; }更多推荐
找到的数量无金额的所有独特的组合
发布评论