回溯算法-整数拆分问题

71 阅读 0 评论 47 点赞

我是靠谱客的博主帅气硬币，这篇文章主要介绍回溯算法-整数拆分问题，现在分享给大家，希望可以做个参考。

洛谷p2404.。。。

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

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

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

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}