题目描述
“天下熙熙,皆为利来;天下攘攘,皆为利往”,监狱里的暗势力划分地盘的目的无非是为了获取利益,他们分配利益的方式是基于这样一个准则:设总利益为自然数N,则任何一个大于1的N,总可以拆分成若干个小于N的自然数之和,求出N的所有拆分后选择最合适的一种进行分配,例如当N=3时,有两种划分,即3=1+2和3=1+1+1。试求出N的所有拆分。
输入
一个整数即N,N<100。
输出
输出每一种划分方案,每种划分方案占一行,最后一行为方案总数。
样例输入 Copy
3
样例输出 Copy
3=1+1+1 3=1+2 2
#include <bits/stdc++.h>
using namespace std;
int n, arr[101];
long long res;
void dfs(int sum, int depth, int start)
{
if (sum > n) return;
if (sum == n)
{
res++;
printf("%d=%d", n, arr[1]);
for (int i = 2; i < depth; i++)
printf("+%d", arr[i]);
sum = 0;
puts("");
return;
}
for (int i = start; i < n; i++)
{
arr[depth] = i;
dfs(sum + i, depth + 1, i);
}
}
int main()
{
scanf("%d", &n);
dfs(0, 1, 1);
printf("%lld\n", res);
return 0;
}