题目：

设计算法， 找出其和等于给定数n的若干自然数的所有可能。 例如， 若n=4， 有5种可能：

1 + 1 + 1 + 11 + 1 + 21 + 32 + 24

解析

方法一：深度优先搜索

参考：https://blog.csdn.net/qq_45159762/article/details/104547304

网上关于整数分解的问题基本是采用深度优先搜索。

关于深度优先搜索 此题是深度优先搜索算法的变形，除去了访问标志。 首先回顾下什么是深度优先搜索。 以此题为背景，以N=3为例，则从1开始一直搜索，搜索到11，再搜索1，即状态为1 1 1，发现满足要求，返回上一层，状态变成1 1，再搜索2，即状态变为1 1 2，发现当前和超过3，返回上一层，状态变为1 1 ，再搜索3，以此类推，直到搜索到N=3，返回上一层变为1 1，因为搜索N个搜索完了，再返回上一层状态变为1。 至此，1 1开头，后一位为试探数已经试探完毕，故1 2开头，搜索，直到N=3,1,3开头。。。最后返回到1，1变为2，以2开头。。。依次类推，其本质为对N做一个全排列，总数为N！ 这就是所谓的 试探回溯法，先逐层试探，满足条件了再逐层回溯。

c++实现：

#include<bits/stdc++.h> using namespace std; int N,sum=0,cnt=0; int result[31],pos=-1;//定义试探数组，存放试探数字 void dfs(int x){ if(sum==N){ //如果试探和等于待匹配数 cnt++; //成功次数+1 cout<<N<<'='; for(int i=0;i<pos;i++){ //输出试探数 cout<<result[i]<<'+'; } if(cnt%4==0||result[pos]==N){//判定最后一个试探数的情况 //如果成功次数为4的倍数或者试探数等于待匹配数 cout<<result[pos]<<endl;//输出试探数并换行 } else{ cout<<result[pos]<<';';//否则按格式输出 } return; } else if(sum>N){//如果试探和大于待匹配数，则返回到上一层 return; } for(int i=x;i<=N;i++){//范围从输入参数，即上一层传进来的试探数开始到待匹配数 result[++pos]=i; // 指针指向下一位置并保存当前变量为试探数 sum+=i; //试探和累加试探数 dfs(i); //递归试探 sum-=i; //试探完后减去试探数，以待下一循环加上新的试探数来试探 pos--; //指针回复到原来的位置，以待下一次自增并保存新的试探数 // pos=0 result[0]; sum=1; dfs(1); sum=0; }//注意，sum,pos作为全局变量，在连续递归调用的情况下会一直自增，故无需担心自增后马上被减去 } int main(){ cin>>N; dfs(1); return 0; }

方法二：递归方法

【思路】 第一个数可以考虑从1到n中的任何一个数k。 第二个数可以考虑从1到剩下的数（n-k）中的任何一个数，以此类推。 直到剩下的数小于等于0为止。若剩下的数等于0，则正好是一个可行解；若小于0，则不予考虑。 被选中的数放在一个字符串中（作为参数）

python实现：

def decompose(n, k, s): # n是和，k是从第k个数开始算起，s是记录和的内容 if n < 0: return 0 elif n == 0: print(s) return 1 else: sum = 0 for i in range(k, n+1): sum += decompose(n-i, i, s+'+'+str(i)) return sum print("n=4时，共%d种可能" % decompose(4, 1, '4=')) print("n=5时，共%d种可能" % decompose(5, 1, '5='))