博客

正整数 n 所有可能的和式的组合（如； 4=1+1+1+1、 1+1+2、 1+3、2+2、4）

代码的思想是，从最小值开始，依次加入序列中，整体类似DFS（深搜），因为有回退的一步。区别是加入一个值s，代表可加入序列的最小值。


代码：

vector<int> v;
vector<vector<int>> vv;

void fun(int val,int s)
{
	if (val == 0) {
		vv.push_back(v);
		return;
	}
	for (int i = s; i <= val; i++)
	{
		v.push_back(i);
		fun(val - i,i);
		v.pop_back();
	}
}

int main()
{
	fun(10,1);
	for (int i=0;i<vv.size();i++)
	{
		for (int j = 0; j < vv[i].size(); j++
			cout << vv[i][j];
		cout << endl;
	}
	return 0;
}

输出：

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 3
1 1 1 1 1 1 2 2
1 1 1 1 1 1 4
1 1 1 1 1 2 3
1 1 1 1 1 5
1 1 1 1 2 2 2
1 1 1 1 2 4
1 1 1 1 3 3
1 1 1 1 6
1 1 1 2 2 3
1 1 1 2 5
1 1 1 3 4
1 1 1 7
1 1 2 2 2 2
1 1 2 2 4
1 1 2 3 3
1 1 2 6
1 1 3 5
1 1 4 4
1 1 8
1 2 2 2 3
1 2 2 5
1 2 3 4
1 2 7
1 3 3 3
1 3 6
1 4 5
1 9
2 2 2 2 2
2 2 2 4
2 2 3 3
2 2 6
2 3 5
2 4 4
2 8
3 3 4
3 7
4 6
5 5
10