- 1:2.深度优先搜索
- 2:3.解题
- 2.1:正解（升序+不去重）
- 2.2:（去重+升序）
@TOC
# 前言
之前看了好多文章都说学习编程时写博客的重要，但一直没有尝试，今天在这发第一篇来开个头吧。
这篇是我刷洛谷时的一道题，希望大家多多指教QAQ
刚刚大一，第一篇记录如下?
一、题目
# 二、解题思路
## 1.考察方向
这道题题目理解很简单，自然数拆分，但要是用单纯循环却很难解决。因此我们想到dfs深搜（深度优先搜索）进行解题。这道题是一道很典型的dfs入门题型，由此可以引发许多变式。
2.深度优先搜索
简介
深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
这么多不如一张图：
我的dfs模版（深搜回溯）
search(i){
for(所有算子）{
if（条件成立） 输出；
else search（i+1）；
回溯
}
}
}
3.解题
正解（升序+不去重）
#include<stdio.h>
int a[100];
int n;
void print(int j)//输出数据
{
for(int i=0;i<=j;i++)
{
if(i==0) printf("%d",a[i]);
else printf("+%d",a[i]);
}
printf("\n");
}
void search(int sum,int j ,int s)//dfs深搜
{
for(int i=s;i<=n;i++)//从第s个开始搜，i=s保证是升序
{sum+=i;
if(sum>n) return;
if(sum==n) {a[j]=i;print(j);return;}
a[j]=i;
search(sum,j+1,i);
sum-=i;//回溯
}
}
int main()
{
while(scanf("%d",&n))//连续输入
{
search(0,0,1);
}
return 0;
}
运行截图
我们这题中运用回溯的技巧，即sum -= i，在搜索中，不要过多注意细枝末节，宏观分析函数总体功能。
什么在控制升序？
我们可以从 for(int i=s;i<=n;i++) 看出，我们在“播撒”算子的时候，起始时在控制是否升序，倘若我用
for(int i=1;i<=n;i++)即不要s变量 ，这样的结果为
我们可以画图理解。
（去重+升序）
#include<stdio.h>
int book[100];
int a[100];
int n;
void print(int j)
{
for(int i=0;i<=j;i++)
{
if(i==0) printf("%d",a[i]);
else printf("+%d",a[i]);
}
printf("\n");
}
void search(int sum,int j,int s)
{
for(int i=s;i<=n;i++)
if(book[i]==0){sum+=i;
if(sum>n) return;
if(sum==n) {a[j]=i;print(j);return;}
a[j]=i;
book[i]=1;
search(sum,j+1,i);
book[i]=0;
sum-=i;
}
}
int main()
{
while(scanf("%d",&n))
{
search(0,0,1);
}
return 0;
}
此结果为
在这里，我们又更进一步运用回溯的作用，用book【】建立判断数组来判断每个数是否取过，若取过，则在此记录数组a【】处标1，直到最后走到枝节末端向上时return一级回溯为0一次，以此类推，即可知数是否取过。
总结
在此题中不仅运用深搜，而且还有回溯的小技巧，对于像我一样的新手是一个很好的练习。
望多多指教