http://bbs.csdn.net/topics/90040267

以上是讨论的论坛

 

下面是一个算法：

//数字为n，开始分解第k个数字void decompose(int n,int k){int i,j;//j用来表示数字是否分解完毕for(j=n;j>=1;j--){a[k]=j;if(j==n){for(int temp=1;temp<=k;temp++)cout<<a[temp]<<" ";cout<<endl;}elsedecompose(n-j,k+1);}}

分解10的结果如下：

时间复杂度实在是有点高。

下面是改进的。

//n为带分解的数字，k为a的
void findN(int n,int k)
{int j;if(n<=0)return;for(j=1;j<=n;j++){a[k]=j;if(a[k]<a[k-1])//分解出来的数字小于之前的数字时候，跳到下一个数字上 即执行j++continue;if(j==n){for(int temp=1;temp<=k;temp++)cout<<a[temp]<<" ";cout<<endl;}else{findN(n-j,k+1);}}
}

可以看见时间从266降低到了12。

所以在递归中一定要加好条件，否则就会出现重复，时间复杂度也降不下来。