找到的数量无金额的所有独特的组合

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