7-37 整数分解为若干项之和 分数 20 作者 DS课程组 单位 浙江大学 将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的...

题目描述

将一个正整数 N 分解成若干个正整数之和，输出所有的分解方式。

输入格式

一个正整数 N。

输出格式

每行输出一种分解方式，每种分解方式按照从大到小的顺序输出。

样例输入

7

样例输出

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

算法1

(回溯算法) $O(n!)$

首先我们可以发现，所有的分解方式的第一个数都不会小于 $\lfloor \frac{N}{2} \rfloor$，因为如果第一个数小于 $\lfloor \frac{N}{2} \rfloor$，那么第二个数至少为 $\lfloor \frac{N}{2} \rfloor$，那么第一个数和第二个数的和就已经大于等于 N 了，不符合要求。

接着，我们可以借助回溯算法来求解。具体方法是，首先设当前的数字为 N，从 $\lfloor \frac{N}{2} \rfloor$ 开始依次枚举第一个数 num，然后递归处理剩下的数字 $N-num$，直到 N 为 0，表示已经找到了一种分解方法。注意，我们为了避免重复，下一次递归的起始数字应该为上一次递归的数字，即从 num 开始枚举。

时间复杂度

最坏情况下，如果 N 为质数，那么分解方式的数量为 $(2^{N-1}-1)$，时间复杂度为 $O((2^{N-1}-1) \times N)$。但实际上，分解方式的数量不会超过 $2^N$，因此时间复杂度可以近似看作 $O(2^N \times N)$。

C++ 代码

class Solution {
public:
void dfs(int n, int start, vector<int>& path, vector<vector<int>>& res) {
if (n == 0) {
res.push_back(path);
return;
}
for (int i = start; i <= n; i++) {
path.push_back(i);
dfs(n - i, i, path, res);
path.pop_back();
}
}

vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
vector<int> path;
dfs(n, 2, path, res);
return res;
}
};

算法2

(暴力枚举) $O(n^2)$

我们可以将分解出来的数字存储在数组中，每次从数组的最后一位开始减去 1，直到当前的数字为 0，表示找到了一种分解方式。不断枚举数字的过程可以通过两层循环实现。

时间复杂度

最坏情况下，如果 N 为质数，那么分解方式的数量为 $(2^{N-1}-1)$，时间复杂度为 $O((2^{N-1}-1) \times N^2)$。但实际上，分解方式的数量不会超过 $2^N$，因此时间复杂度可以近似看作 $O(2^N \times N^2)$。

C++ 代码

class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
vector<int> path(n, 1);
while (path[0] <= n / 2) {
int sum = accumulate(path.begin(), path.end(), 0);
if (sum == n) res.push_back(path);

int i = n - 1;
while (i >= 0 && path[i] == 1) i--;
if (i < 0) break;

int j = i;
while (j >= 0 && path[j] == path[i]) j--;
path[j]++;
for (int k = j + 1; k <= i; k++) path[k] = path[j];
}
return res;
}
};