蓝桥杯 算法提高 自然数拆分 回溯

题目

HJQ同学发现了一道数学题，要求n拆分成若干自然数和的方案
输入格式
　　输入n
输出格式
　　输出n拆分成若干自然数和的方案，每个方案一行
数据规模和约定
　　n <= 10
资源限制
内存限制：256.0MB C/C++时间限制：1.0s

思路

如图树形结构，回溯+剪枝。

代码

#include 
using namespace std;
#include 
#include 
vector<int> v;
vector<int> path;

void backtracking(int n,int startIndex)
{
	
	if (accumulate(path.begin(), path.end(), 0) == n)
	{
		if (path.size() == 1)
			return;

		for (int i = 0; i < path.size() - 1; i++)
		{
			cout << path[i] << "+";
		}
		cout <<path[path.size()-1] << endl;
		return;
	}

	for (int i = startIndex;i < n;i++)
	{
		if (accumulate(path.begin(), path.end(), 0) < n)	//剪枝
		{
			path.push_back(v[i]);
			backtracking(n,startIndex++);					//递归
			path.pop_back();								//回溯
		}
		else break;
	}
}

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		v.push_back(i+1);
	}
	backtracking(n,0);
	return 0;
}

总结

1、我终于知道我写的代码与模板的区别，一个是我把startIndex加1 *** 作放在递归中，模板是放在 i 中的；一个是求和的地方，因为我用的是accumulate函数计算path，并没有放在参数，所以也回溯不了sum【应该是的吧，我也不太确定】，搞得我想背回溯问题模板了，毕竟回溯也就这几种。

【毕竟，子集问题和这道题的代码我应该可以记住】
2、在哪剪枝，这是一个问题；有几种剪枝手法，这是一个问题。

3、最近终于学会了以前一直想搞的DeBug，有一点开心。