对于给定的整数a，找到总和为a的正整数的所有唯一组合 [英] For a given integer a, find all unique combinations of positive integers that sum up to a

问题描述

不是作业问题. 我在此处进行了提问，然后遇到了这个问题. 有人回答了.我已经尝试了很多，以了解所使用的递归，但我无法获得它.有人可以向我解释吗?

Not a homework question. I was going through the questions here and I came across this question. Someone has answered it. I have tried a lot to understand the recursion used but I am not able to get it. Could someone explain it to me?

为给定的数字编写一个函数，通过使用加法以及等于或小于此数字且大于零的任何数字，打印出所有不同的方法来生成该数字.

Write a function, for a given number, print out all different ways to make this number, by using addition and any number equal to or smaller than this number and greater than zero.

例如，给定a = 5，我们有以下7种方式构成5:

For example, given a = 5, we have the following seven ways to make up 5:

• 1，1，1，1，1
• 1、4
• 1、1、1、2
• 1、1、3
• 2、3
• 1、2、2
• 5

该站点的解决方案使用C ++:

The solution from the site is in C++:

void printSeq( int num , int a[] , int len , int s )
{
    if( num <= 0 )
    {
        for( int j = 0 ; j < len ; j++ )
            cout << a[ j ] << "," ;
        cout << endl;

        return;
    }

    for(int i = s ; i <= num ; i++)
    {
        a[ len ] = i;
        printSeq( num - i , a , len + 1 , i );
    }
}

int main()
{
    int a[5];
    printSeq(5,a,0,1);
    cin.get();
    return 0;
} 

推荐答案

遇到此类问题时，通常最好退一步，从编辑器/IDE退后一步，通过画一个简单的案例来思考问题.在白板上.甚至都不需要做伪代码，只需绘制一个流程图，说明此问题的简单情况(例如a = 3)将如何一直消失.另外，一开始不必担心重复的组合.尝试找到可以为您提供所有所需组合的解决方案，然后改进您的解决方案以免出现重复.在这种情况下，为什么不查看a = 3的可管理情况?让我为您画些图画.绿色的对勾标记表示我们已到达有效的组合，红色的叉号表示组合无效.

When facing a problem like this it is often a good idea to take a step back from your editor/IDE and think about the problem by drawing out a simple case on a whiteboard. Don't even do pseudo-code yet, just draw out a flowchart of how a simple case (e.g. a = 3) for this problem would turtle all the way down. Also, don't worry about duplicate combinations at first. Try to find a solution which gives you all the desired combinations, then improve your solution to not give you duplicates. In this case, why not look at the manageable case of a = 3? Let me draw a little picture for you. A green checkmark means that we have arrived at a valid combination, a red cross means that a combination is invalid.

如您所见，我们从三个空的子组合开始，然后通过在每个子组合后附加一个数字来构建三个新的子组合.我们要检查所有可能的路径，因此我们选择1、2和3，最后得到[1]，[2]和[3].如果组合中的数字总和等于3，则说明我们找到了有效的组合，因此可以停止检查此路径.如果组合中数字的总和超过3，则该组合无效，我们也可以停止.如果两者都不是，我们将继续构建组合，直到得出有效或无效的解决方案.

As you can see, we start with three empty subcombinations and then build three new subcombinations by appending a number to each of them. We want to examine all possible paths, so we choose 1, 2 and 3 and end up with [1], [2] and [3]. If the sum of the numbers in a combination equals 3, we have found a valid combination, so we can stop to examine this path. If the sum of the numbers in a combination exceeds 3, the combination is invalid and we can stop as well. If neither is the case, we simply continue to build combinations until we arrive at either a valid or invalid solution.

由于您的问题似乎主要是关于如何针对此类问题制定递归解决方案，而与特定语法无关，而您恰巧找到了C ++解决方案，因此我将在Python中提供一个解决方案(看起来就像伪代码，这就是它所知道的.)

Since your question seems to be primarily about how to work out a recursive solution for this kind of problems and less about specific syntax and you just happened to find a C++ solution I am going to provide a solution in Python (it almost looks like pseudo code and it's what it know).

def getcombs(a, combo = None):
    # initialize combo on first call of the function
    if combo == None:
        combo = []

    combosum = sum(combo) # sum of numbers in the combo, note that sum([]) == 0
    # simple case: we have a valid combination of numbers, i.e. combosum == a
    if combosum == a:
        yield combo # this simply gives us that combination, no recursion here!
    # recursive case: the combination of numbers does not sum to a (yet)
    else:
        for number in range(1, a + 1): # try each number from 1 to a               
            if combosum + number <= a:  # only proceed if we don't exceed a
                extcombo = combo + [number] # append the number to the combo
                # give me all valid combinations c that can be built from extcombo
                for c in getcombs(a, extcombo):
                    yield c

让我们测试一下代码！

>>> combos = getcombs(3)
>>> for combo in combos: print(combo)
... 
[1, 1, 1]
[1, 2]
[2, 1]
[3]

这似乎工作正常，是a = 5的另一项测试:

This seems to work fine, another test for a = 5:

>>> combos = getcombs(5)
>>> for combo in combos: print(combo)
... 
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3]
[1, 2, 1, 1]
[1, 2, 2]
[1, 3, 1]
[1, 4]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 3]
[3, 1, 1]
[3, 2]
[4, 1]
[5]

该解决方案包含了我们一直在寻找的所有七个组合，但是代码仍然会产生重复.您可能已经注意到，不必使用小于先前选择的数字的数字来生成所有组合.因此，让我们添加一些代码，这些代码仅开始为不小于组合中当前最后一个数字的数字建立extcombo.如果组合为空，则只需将前一个数字设置为1.

The solution includes all seven combinations we were looking for, but the code still produces duplicates. As you may have noticed, it is not necessary to take a number smaller than the previous chosen number to generate all combinations. So let's add some code that only starts to build an extcombo for numbers which are not smaller than the currently last number in a combination. If the combination is empty, we just set the previous number to 1.

def getcombs(a, combo = None):
    # initialize combo on first call of the function
    if combo == None:
        combo = []

    combosum = sum(combo) # sum of numbers in combo, note that sum([]) == 0
    # simple case: we have a valid combination of numbers, i.e. combosum == a
    if combosum == a:
        yield combo # this simply gives us that combination, no recursion here!
    # recursive case: the combination of numbers does not sum to a (yet)
    else:
        lastnumber = combo[-1] if combo else 1 # last number appended
        for number in range(lastnumber, a + 1): # try each number between lastnumber and a
            if combosum + number <= a:
                extcombo = combo + [number] # append the number to the combo
                # give me all valid combinations that can be built from extcombo
                for c in getcombs(a, extcombo):
                    yield c

再次，让我们测试一下代码！

Once again, let's test the code!

>>> combo = getcombs(5)
>>> for combo in combos: print(combo)
... 
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]

提出的解决方案可能不是最有效的解决方案，但希望它将鼓励您进行递归思考.逐步分解问题，为小额投入制定一个简单案例，并一次解决一个问题.

The presented solution may not be the most efficient one that exists, but hopefully it will encourage you to think recursively. Break a problem down step by step, draw out a simple case for small inputs and solve one problem at a time.

这篇关于对于给定的整数a，找到总和为a的正整数的所有唯一组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！