找到的数量无金额的所有独特的组合 [英] Find all unique combinations of sum of a Number N

问题描述

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

这篇关于找到的数量无金额的所有独特的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！