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,我们有以下七种方法来弥补5：
> 1,1,1@H_301_2@> 1,4@H_301_2@> 1,2@H_301_2@> 1,3@H_301_2@> 2,3@H_301_2@> 1,2,2@H_301_2@> 5
该网站的解决方案是在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,1);
cin.get();
return 0;
}
解决方法
如您所见,我们从三个空子组合开始,然后通过向每个子组合附加一个数字来构建三个新的子组合.我们想要检查所有可能的路径,因此我们选择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,2] [2,1] [3]
这似乎工作正常,a = 5的另一个测试：
>>> combos = getcombs(5) >>> for combo in combos: print(combo) ... [1,2] [1,3] [1,3,4] [2,1] [2,3] [3,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,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,3] [5]
提出的解决方案可能不是最有效的解决方案,但希望它会鼓励您递归思考.逐步解决问题,为小输入绘制一个简单的案例,一次解决一个问题.
