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,有一点开心。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)