文章目录
题目
将一个正整数 N N 分解成几个正整数相加，可以有多种分解方法，例如 7 = 6 + 1 ， 7 = 5 + 2 ， 7 = 5 + 1 + 1 ， … 7=6+1，7=5+2，7=5+1+1，… 编程求出正整数N的所有整数分解式子。
输入格式
每个输入包含一个测试用例，即正整数 N （ 0 < N ≤ 30 ） N （0 < N ≤ 30） 。
输出格式
按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列 N 1 = N_1 = { n 1 , n 2 . . . . . . n_1,n_2...... } 和 N 2 = N_2 = { m 1 , m 2 . . . . . . m_1,m_2...... } ，若存在 i i 使得 n 1 = m 1 ， . . . . . . ， n i = m i n_1 = m_1，......，n_i = m_i ，但是 n i + 1 < m i + 1 n{i+1} < m ，则 N 1 N_1 序列必定在 N 2 N_2 序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出 4 4 个式子后换行。
输入样例
7
输出样例
7=1+1+1+1+1+1+1；7=1+1+1+1+1+2；7=1+1+1+1+3；7=1+1+1+2+2
7=1+1+1+4；7=1+1+2+3；7=1+1+5；7=1+2+2+2
7=1+2+4；7=1+3+3；7=1+6；7=2+2+3
7=2+5；7=3+4；7=7
题解
解题思路
这道题是深度优先搜索的变形，首先输入一个数字，然后从 1 1 开始深度搜索，然后用 f o r for 循环进行将数存入数组，再相加，在进行深搜，直至总和等于 n n 就输出。
完整代码
#include<iostream> using namespace std; int n, sum, num; // sum 用于记录此时累加的和，num 是数组 A 的指针 int A[30], cnt = 1; // 数组 A 用于存储加数，cnt 用于计算已经输出的答案的数量 void DFS(int k) { // 深度优先算法 if( sum > n ) return; if( sum == n ) { cout << n << "="; for(int i = 0; i < num; i ++) { if(i != 0) cout << "+"; cout << A[i]; } if(cnt % 4 == 0 ) // 每逢输出四组答案换行； cout << endl; else{ if(A[0] != n) // a[0] = n 一定为最后一项答案，不需要分号； cout << ";"; } cnt ++; return; } for(int i = k; i <= n; i ++) { sum += i; A[num++] = i; DFS(i); num --; sum -= i; } } int main(void) { cout << "请输入一个正整数："; // 提交时注释此行 cin >> n; DFS(1); return 0; }