来源：http://blog.csdn.net/u012492780/article/details/21558005
题目大意：给定一个整数n，找到k个数，使得其和等于n。
解题思路：要分解整数n，肯定先要找到一个因子，然后我们会发现，剩下的问题还是一个整数分解问题，因此容易得到问题的解。 定义函数f(n)为n可以分解的解的个数，即可以先分解出一个数字k(k = 0,1,2，……，n)，然后再分解f(k)，可以得出有： f(n) = f(n-1) + f(n-2) + ……+ f(1) + f(0)，其中f(0) = 1 于是可以解得f(n) = 2^(n-1) ，n>=1
下面附代码将每组解打印出来，并验证上述式子，代码如下：
[cpp] view plain copy #include <iostream> using namespace std; #define MAX 20 int res_num; // 因子暂存在res数组中 int res[MAX]; int p_res = 0; // 将n进行分解 void resolve(int n); int main() { while (1) { int n; cin >> n; resolve(n); cout << "total num of res:\t" << res_num << endl; res_num = 0; } return 0; } void resolve(int n) { if (n<=0) { // 出口 for (int i=0; i<p_res; i++) cout << res[i] << " "; cout << endl; res_num++; } for (int i=1; i<=n; i++) { res[p_res] = i; p_res++; // p_res++来顺次存储各个因子 resolve(n-i); p_res--; // 此行必须有，执行完上一行，下一次for循环即使第一个因子 } } 可以发现上述代码输出的结果有重复答案，如当n=4时，会输出1 3，和3 1两组解，其实他们是相同的。如果要求答案不能重复呢？
同样，我们可以定义一个函数f(n, min_factor)，其中min_factor表示n分解后因子中的最小值，这样即可通过min_factor来限制for循环的初始值，达到因子从小到大输出的目的，从而避免相同的解重复输出
稍微修改上述代码，即可得到解，同样贴出代码如下：
[cpp] view plain copy #include <iostream> using namespace std; #define MAX 20 int res_num; // 因子暂存在res数组中 int res[MAX]; int p_res = 0; // 将n进行分解 void resolve(int n, int min_factor=1); int main() { while (1) { int n; cin >> n; resolve(n); cout << "total num of res:\t" << res_num << endl; res_num = 0; } return 0; } void resolve(int n, int min_factor) { if (n<=0) { // 出口 for (int i=0; i<p_res; i++) cout << res[i] << " "; cout << endl; res_num++; } for (int i=min_factor; i<=n; i++) { // 此处修改 res[p_res] = i; p_res++; // p_res++来顺次存储各个因子 resolve(n-i, i);<span style="white-space:pre"> </span>// 此处修改 p_res--; // 此行必须有，执行完上一行，下一次for循环即使第一个因子 } }其实，如果只要求出分解的解的个数，可以按照如下方法：
定义函数f(n, m)，其中m表示n分解后因子中的最小值，则有
当（n<m）时，即最小因子大于n，则返回0，f(n,m) = 0
当（n==m，即最小因子等于自身）， f(n,m) = 1
其他情况，f(n,m) = f(n,m+1) + f(n-m, m) （即分解的结果可以分为两类，1. 分解后的因子中不包含m，即f(n,m+1)；2. 分解后的因子中包含，即f(n-m, m)，两种情况的结果相加就是结果了）
易知，动态规划可以加速求解，附代码如下：
[cpp] view plain copy #include <iostream> using namespace std; #define MAX 200 int dp[MAX][MAX]; // 将n进行分解 int resolve(int n, int min_factor=1); int main() { while (1) { int n; cin >> n; cout << "total num of res:\t" << resolve(n) << endl; } return 0; } int resolve(int n, int min_factor) { if (min_factor > n) return 0; if (dp[n][min_factor]!=0) return dp[n][min_factor]; if (n == min_factor) { dp[n][min_factor] = 1; return 1; } return dp[n][min_factor] = resolve(n, min_factor+1) + resolve(n-min_factor, min_factor); } 同样也可以用此种方法来打印结果（不过不能使用动态规划了，因为动态规划省略了一些重复的求解过程，这些过程也会产生出结果），代码如下： [cpp] view plain copy #include <iostream> using namespace std; #define MAX 20 // 因子暂存在res数组中 int res[20]; int p_res = 0; // 将n进行分解 int resolve(int n, int min_factor=1); int main() { while (1) { int n; cin >> n; cout << "total num of res:\t" << resolve(n) << endl; } return 0; } int resolve(int n, int min_factor) { if (min_factor > n) return 0; if (min_factor == n) { res[p_res] = min_factor; p_res++; for (int i=0; i<p_res; i++) cout << res[i] << " "; cout << endl; p_res--; return 1; } res[p_res] = min_factor; p_res++; int k = resolve(n-min_factor, min_factor); p_res--; int s = resolve(n, min_factor+1); return k+s; } 进一步，如果要求分解后的因子也要不同，怎么办呢？min_factor不是控制因子的最小值么，将for中对resolve函数的调用改为如下行即可：
[cpp] view plain copy resolve(n-i, i+1); 这样n分解的因子就各不相同了也可以定义f(n, max_factor)来求解，max_factor 为最大因子，其递推公司如下：
当（n<=1 || m==1）时，f(n, max_factor) = 1
当（max_factor > n）时， f(n, max_factor) = f(n, n)
其他情况，f(n, max_factor) = f(n-max_factor, max_factor) + f(n, max_factor-1)
代码就不写了
最后，建议对待递归的出口慎重（我在此犯了小错误），仔细读一下，然后最好动手写一下，毕竟眼过千遍，不如手过一遍
