面试题 整数划分

缘起

题目: 给你一个正整数n，求它所有的整数划分方案. 例如n=5的所有划分方案如下

1
2
3
4
5
6
7
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

如果更进一步, 给你一个限制 _max, 要求你的每一个划分方案中出现的数字都不能超过_max呢? 比如 _max=3, 则5的划分方案减少为

1
2
3
4
5
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

分析

简单的递归而已. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include "stdafx.h"
#include <algorithm>
using namespace std;
const int MAXN=100;//最多求100以内的正整数划分
int a[MAXN]; // 存放划分方案的数组,这里我们要求它是递减的

void foo(int n, int _max, int step) // 当前决定 a[step]放什么
{
	if (!n)
	{
		for (int j = 0;j<step; j++) printf("%d ", a[j]); // a已经把n瓜分完毕, 得到一种整数划分的方案了
		puts("");
		return;
	}
	for (int j = _max; j; j--) // 决定a[step]放什么
	{
		a[step]=j;
		foo(n-j, min(j,n-j),step+1); // 下一步的_max因为 a是递减的, 所以不能超过当前放置的j(<=最初题目给的_max),然后显然也不能超过还剩下的n-j 
	}
}


int main()
{
	foo(90,3,0); // 90的最多<=3的整数划分方案
	return 0;
}