例题，将正整数拆分问题

  1. 将正整数 n 分解成3个正整数，如 6 = 1 + 2 + 3，
  2. 排在后面的数必须大于等于前面的数，输出所有方案。
  4. 上机操作：循环实现
  5. 上机操作：递归实现
  1. 将正整数 n 分解成 小于等于m 个正整数之和，
  2. 且排在后面的数必须 大于等于 前面的数，并输出所有方案。
  5. 输入：
  6. 4 3
  7. 输出： 
  8. 1 1 2 
  9. 1 3 
  10. 2 2 
  11. 4

对于问题1，我们可以使用循环处理，using 3 loops

  1. for (int i = 1; i <= n; ++i)
  2.   for (int j = i; j <= n; ++j)
  3.     for (int k = j; k <= n; ++k)
  4.       if (i + j + k == n) printf("%d=%d+%d+%d\n", n, i, j, k);

如果问题变成“将正整数n分解成4个正整数”，此时就需要4重循环。如果问题变成“分解成小于等于m个整数”，那么，就没办法使用loops去弄了，需要使用递归搜索。

下面，我们考虑问题2。（用搜索树，来表示）

我们将问题分层，第 i 层决定 ai。则为了进行第 i 层决策，我们需要记录三个状态变量：

  • 表示后面所有正整数的和
  • 表示前一层的正整数，以确保正整数递增
  • 分解了几个数，确保我们最多输出 m 个正整数
  1. // arr[]记录方案
  2. void dfs(int n, int i, int last) {
  3.   if (n == 0) {
  4.     //输出方案
  5.   }
  7.   if (i <= m) {
  8.     for (int j = last; j <= n; j++) {
  9.       arr[i] = j;
  10.       dfs(n - j, i + 1, j);  //剩余n-j, 分解了i+1个数，前一个数用的是j
  11.     }
  12.   }
  13. }
  15. dfs(n, 1, 1);

示例程序

  1. // 将正整数n分解成 小于等于m个 正整数之和，且排在后面的数必须大于等于前面的数，并输出所有方案
  2. #include <bits/stdc++.h>
  4. using namespace std;
  6. int n, m;
  7. int a[110];
  9. void dfs(int left, int u, int prev)
  10. {
  11.     if (left == 0){
  12.         for (int i = 1; i < u; i++) printf("%d ", a[i]);
  13.         puts("");
  15.         return ;
  16.     }
  18.     if (u > m) return ;
  20.     for (int i = prev; i <= left; i++){
  21.         a[u] = i;
  22.         dfs(left - i, u + 1, i);
  23.     }
  24. }
  26. int main()
  27. {
  28.     cin >> n >> m;
  29.     dfs(n, 1, 1);  //剩余n可分配，当前第1位，可以从1开始用
  31.     return 0;
  32. }
  1. //把n恰好分成m个正整数的方案，问题1的递归实现
  2. #include <bits/stdc++.h>
  4. using namespace std;
  6. int n, m;
  7. int a[110];
  9. void dfs(int left, int u, int prev)
  10. {
  11.     if (left == 0){
  12.         if (u == m + 1){
  13.             for (int i = 1; i < u; i++) printf("%d ", a[i]);
  14.             puts("");
  15.         }
  17.         return ;
  18.     }
  20.     if (u > m) return ;
  22.     for (int i = prev; i <= left; i++){
  23.         a[u] = i;
  24.         dfs(left - i, u + 1, i);
  25.     }
  26. }
  28. int main()
  29. {
  30.     cin >> n >> m;
  31.     dfs(n, 1, 1);  //剩余n可分配，当前第1位，可以从1开始用
  33.     return 0;
  34. }
  1. //重新设计一个dfs函数，这回是带用了多少作为参数
  2. //把n恰好分成m个正整数的方案，问题1的递归实现
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. int n, m;
  8. int A[110];
  10. void dfs(int u, int sum, int a)  //当前第u个，已经分配了sum，可以从a开始用
  11. {
  12.     if (u == m + 1)
  13.     {
  14.         if (sum == n){
  15.             for (int i = 1; i <= m; i++) printf("%d ", A[i]);
  16.             puts("");
  17.         }
  19.         return ;
  20.     }
  22.     for (int j = a; j <= n; j++){
  23.         A[u] = j;
  24.         dfs(u + 1, sum + j, j);
  25.     }
  26. }
  28. int main()
  29. {
  30.     cin >> n >> m;
  31.     dfs(1, 0, 1); 
  32.     return 0;
  33. }