算法—-回溯（附录—剪枝）

回溯相信大家都已经了解了所以这章我将见但介绍下回溯剪枝

为什要剪枝

在《算法—-回溯（正文）》中我提到过回溯就是暴力，为什么那些题能过，因为数据范围小
那如果数据范围大了，就不行了，这时剪枝的作用就出来了，去除重复多余，不符合的把时间复杂度降下来

什么是剪枝

将不需要的删除，不考虑

回溯剪枝模板

void dfs(变量){if(终止条件){存放结果return ;} 判断（剪枝）(1.如果这都不符合了那么后面肯定不符合2.重复的东西有了就可以不要了) for(.....){判断标记dfs();回溯 } }

回溯剪枝例题

1318：【例5.3】自然数的拆分
【题目描述】
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

当n=7共14种拆分方法：

7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14
【输入】
输入n。

【输出】
按字典序输出具体的方案。

【输入样例】
7
【输出样例】
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4

#includeusing namespace std;int n;int ab[350];void print(int cnt){cout<<n<<"=";bool f=false;for(int i=1;i<=cnt;i++){if(f){cout<<"+";}cout<<ab[i];f=true;} cout<<"\n";}void dfs(int cnt,int s,int last){for(int i=last;i<n;i++){if(s-i==0){ab[cnt]=i;print(cnt);return ;}else if(s-i>0){ab[cnt]=i;dfs(cnt+1,s-i,i);}}}int main(){cin>>n;dfs(1,n,1);return 0;}//不减枝

#includeusing namespace std;int n;int ab[350];void print(int cnt){cout<<n<<"=";bool f=false;for(int i=1;i<=cnt;i++){if(f){cout<<"+";}cout<<ab[i];f=true;} cout<<"\n";}void dfs(int cnt,int s,int last){for(int i=last;i<n;i++){if(s-i==0){ab[cnt]=i;print(cnt);return ;}else if(s-i>0){ab[cnt]=i;dfs(cnt+1,s-i,i);}else{break;}}}int main(){cin>>n;dfs(1,n,1);return 0;}//剪枝

总结：剪枝对于小数据来说不算啥，但对于大数据就很重要了