题目:
利用递归算法输出正整数和为n的所有不增的正整数和式。例如当n=5时,不增的和式如下:
5=5
5=4+1
5=3+2
5=3+1+1
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
解题思路:
形如这种求子集的问题都可以采用回溯法来解决,回溯法即一种加上剪枝判断的递归算法。
解决问题的关键词:不增
代码实现:
数组a用来保存分解出来的和数,即某个分解的集合
sum表示需要分解的数
k表示要分解的第k个和数
#include <iostream>
#include <stdio.h> using namespace std; #define N 100 void subSetOfSumN(int a[],int sum,int k){
for(int i=sum;i>=;i--){
if(i<=a[k-]){
a[k]=i;
if(i==sum){
printf("%d=%d",a[],a[]);
for(int p=;p<=k;p++)
printf("+%d",a[p]);
printf("\n");
}
else
subSetOfSumN(a,sum-i,k+);
}
}
} int main()
{
int n,a[N];
printf("Please input an integer n(1<=n<=20):");
scanf("%d",&n);
a[]=n;
printf("The result of nonDescend integer factorization is:\n");
subSetOfSumN(a,n,);
return ;
}