对于给定的整数a,找到总和为a的所有唯一正整数组合

Question

不是作业问题.我在这里问题,我遇到了这个问题.有人回答了.我已经尝试了很多来理解使用的递归,但我无法得到它.有人可以向我解释一下吗？

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

例如,给定a = 5,我们有以下七种方法来弥补5:

• 1,1,1,1,1
• 1,4
• 1,1,1,2
• 1,1,3
• 2,3
• 1,2,2
• 五

该网站的解决方案是在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;
} 

Answer 1

当遇到这样的问题时,通常从编辑器/ IDE退一步并通过在白板上绘制一个简单的案例来思考问题通常是个好主意.甚至不做伪代码,只是绘制一个流程图,说明a = 3这个问题的一个简单案例(例如)将如何一直向下.此外,首先不要担心重复组合.尝试找到一个解决方案,为您提供所有需要的组合,然后改进您的解决方案,不给您重复.在这种情况下,为什么不看看可管理的情况a = 3呢？让我为你画一幅画.绿色复选标记表示我们已达到有效组合,红叉表示组合无效.

如您所见,我们从三个空子组合开始,然后通过向每个子组合附加一个数字来构建三个新的子组合.我们想要检查所有可能的路径,因此我们选择1,2和3并最终得到[1],[2]和[3].如果组合中的数字总和等于3,我们找到了一个有效的组合,所以我们可以停下来检查这条路径.如果组合中的数字总和超过3,则组合无效,我们也可以停止.如果不是这种情况,我们只是继续构建组合,直到我们得出有效或无效的解决方案.

因为你的问题似乎主要是关于如何为这类问题制定递归解决方案而不是特定语法,你刚刚找到了一个C++解决方案我将提供一个Python解决方案(它几乎看起来像伪代码它就是它所知道的.

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:

>>> 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.

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

再一次,让我们测试代码吧!

>>> 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]

提出的解决方案可能不是最有效的解决方案,但希望它会鼓励您递归思考.逐步解决问题,为小输入绘制一个简单的案例,一次解决一个问题.

Answer 2

暂时把解决方案放在一边，看看问题本身：

将此问题与数组的插入排序（或任何递归算法）进行比较。在插入排序中，在执行过程中的任何时刻，我们都有一部分已排序的数组和另一部分未排序的。我们从未排序的部分中选取一个元素，并找到它在已排序的部分中的位置，从而扩展已排序的部分，使问题变得更小。

对于这个问题，我们可以从整数 1 到问题中的数字（我们称之为 N）中选择固定数量的元素，作为总和为 N 的序列的一部分。

在任何时候，我们都会收集一些总和小于 N（例如 X）的数字，将问题减少到 NX 大小，同时将下一次递归的选择从 1..N 减少到 1..(NX)。

该解决方案的作用很明显，从 1 到 (NX) 进行每个选择，并递归进行直到 X=N。每当算法达到 X=N 时，就意味着找到了一个排列。

注意：我看到该解决方案的一个问题是它需要事先知道将找到的排列数量。 int a[5]; 如果该值未知，这可能会导致问题。