将一个数分解成多个加数相加的形式

看到这个命题首先想到的是暴力递归，除了这个办法看起来好像没有更好的办法。。。不知道是不是。

举个栗子：比如 4

首先想到的是1+1+1+1，来抽象一下，数字n，它的所有组合情况一定是这样的：

1+f(n-1)

2+f(n-2)

3+f(n-3)

..................

n-1+f(1)

哈哈，有没有看到一丝规律呢，其实递归退出条件都被你看到了。

再往下写一个  f(n-1) = 1+f(n-1-1) 

哈哈哈，仿佛看到了亮闪闪的for循环，你说对了，每次递归初始值都是从1开始的，终止条件呢，当然是本层栈待求变量的最大值喽，是这样吗？

实践一下就知道了

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MIN(X,Y) (((X)<(Y))?(X):(Y))

void WriteBuffer(const int * buffer)
{
	while (buffer[1] != 0)
	{
		printf("%d+", *buffer++);
	}
	printf("%d\n", *buffer);
}

void _splitnum(int * buffer, const int x, const size_t pos)
{
	if (x <= 1)
	{
		buffer[pos + 1] = x;
		buffer[pos + 2] = 0;
		WriteBuffer(buffer);
	}
	else
	{
		size_t npos = pos + 1;
		for (int i = 1; i <= x; i++)
		{
			buffer[npos] = i;
			_splitnum(buffer, x - i, npos);
		}
	}
}

void SplitNum(const int x)
{
	if (x <= 0) return;
	int * buffer = (int*)malloc(sizeof(int) * (x + 1));
	for (int i = 1; i < x; i++)
	{
		buffer[0] = i;
		_splitnum(buffer, x - i, 0);
	}
}

int main()
{
	int x = 0;
	 
	cin >> x;
	SplitNum(x);
	system("pause");
 
}

4
1+1+1+1
1+1+2
1+2+1
1+3
2+1+1
2+2
3+1

我们发现有重复的组合，观察一下重复序列的特点，1+1+2 、   2+1+1 什么区别，一个序列后面的值大于前面的值呗，另一个后面的值，都小于第一个值呗，推广一下，还都符合规律，像一个什么办法控制一下呢，将 x 的值控制成序列前面所有值的最小值不就行了吗，min(x,buffer[pos])，完美解决重复的问题

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MIN(X,Y) (((X)<(Y))?(X):(Y))

void WriteBuffer(const int * buffer)
{
	while (buffer[1] != 0)
	{
		printf("%d+", *buffer++);
	}
	printf("%d\n", *buffer);
}

void _splitnum(int * buffer, const int x, const size_t pos)
{
	if (x <= 1)
	{
		buffer[pos + 1] = x;
		buffer[pos + 2] = 0;
		WriteBuffer(buffer);
	}
	else
	{
		size_t npos = pos + 1;
		for (int i = 1; i <= MIN(x, buffer[pos]); i++)
		{
			buffer[npos] = i;
			_splitnum(buffer, x - i, npos);
		}
	}
}

void SplitNum(const int x)
{
	if (x <= 0) return;
	int * buffer = (int*)malloc(sizeof(int) * (x + 1));
	for (int i = 1; i < x; i++)
	{
		buffer[0] = i;
		_splitnum(buffer, x - i, 0);
	}
}

int main()
{
	int x = 0;
	 
	cin >> x;
	SplitNum(x);
	system("pause");
 
}

 4
1+1+1+1
2+1+1
2+2
3+1

读者细细把玩一下吧，递归还是很有趣的。