求和为n的所有组合

Question

给定一个数 n

要求：
（1）等式左边的整数取值为 1~n-1.
（2）要求等式左边之和为n。

若 n = 3;
1 + 1 + 1 = 3;
1 + 2 = 3;

Answer 1

提问前最好能多搜索几下，segmentfault上已有类似提问：https://segmentfault.com/q/10...

有一个答案是DFS的，可以输出具体方案，但是效率较低。
有一个是我的答案，用的是动态规划(DP)，时间复杂度O(N^2)
楼上说的母函数也可以用，但没有DP方便

Answer 2

楼主可以去学习下 母函数

这应该是母函数的模板题