回溯算法-整数拆分问题

洛谷p2404.。。。

简单的回溯法实现，输入一个数字n，求出1到n-1中相加和是n的算式。

用一个ans数组储存探索到的每一个数字，在dfs函数中用减法的形式得到和什么时候到达了n，到达n也就是temp变为0的时候。

同时又根据实例，没有重复的算式，一个数字可以用多次，所以i的起始位置要设置一个start来表示，为什么？

由于一个数可以使用多次，下一层的结点从这个搜索起点开始搜索；

在搜索起点 start 之前的数因为以前的分支搜索过了，所以一定会产生重复。

#include<bits/stdc++.h>
using namespace std;
int n;
void dfs(int start,int temp,vector<int>& ans){
if(temp<0) return;
if(temp == 0){
for(int i=0;i<ans.size();++i){
if(i == 0){
cout<<ans[i];
}
else{
cout<<"+"<<ans[i];
}
}
cout<<endl;
}
for(int i=start; i<n; ++i){
ans.push_back(i);
dfs(i,temp-i,ans);
ans.pop_back();
}
}
int main(){
cin>>n;
vector<int> ans;
dfs(1,n,ans);
system("pause");
return 0;
}

最后

以上就是帅气硬币为你收集整理的回溯算法-整数拆分问题的全部内容，希望文章能够帮你解决回溯算法-整数拆分问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。