“让右手始终贴着左边的墙壁走”
举荐应用递归实现DFS，应用递归的时候零碎会调用零碎栈，因而用递归来实现DFS的实质还是栈
vector罕用函数：
| 函数 | 性能 | 工夫复杂度 |
|---|---|---|
| push_back(x) | 在vector前面增加一个元素 | O(1) |
| pop_back() | 删除vector的尾元素 | O(1) |
| size() | 取得vector的元素个数 | O(1) |
| clear() | 清空vector中的所有元素 | O(N)，N为vector元素个数 |
| insert(it,x) | 向vector的任意迭代器it处插入一个元素x | O(N) |
| erase(it) | 删除迭代器it处的元素 | O(N) |
| erase(first,last) | 删除[first,last)内的所有元素 | O(N) |
上面给出《算法笔记》书本中的两个经典例子
- 背包问题求解留神点（《算法笔记》P272页）
#include <iostream>#include <stdio.h>#include <algorithm>using namespace std;const int maxn = 30;int n=0;int V=0;int maxWeight=0;int maxValue=0;int w[maxn];int v[maxn];void DFS(int index,int sumW,int sumV){ if(index==n){ return; } DFS(index+1,sumW,sumV); if(sumW+w[index]<=maxWeight){//if条件里是<=，等于号不能漏，否则会漏解，可能要完第index号物品后，背包满了，且恰好价值最大 if(sumV+v[index]>maxValue){ maxValue = sumV+v[index]; } DFS(index+1,sumW+w[index],sumV+v[index]); }}int main(){ scanf("%d%d",&n,&maxWeight); for(int i=0; i<n; i++){ scanf("%d",&w[i]); } for(int i=0; i<n; i++){ scanf("%d",&v[i]); } DFS(0,0,0); printf("%d",maxValue); return 0;}- 给定N个整数（可能有正数），从中选取K个数，使得这K个数之和恰好等于一个给定的整数X，如果有多种计划，抉择它们中元素平方和最大的一个（《算法笔记》P273页）
#include <iostream>#include <stdio.h>#include <vector>using namespace std;const int maxn = 10000;int n=0;int k=0;int x=0;int maxSquare=-1;int A[maxn];vector<int> st;vector<int> temp;void DFS(int index,int nowk,int sum,int sumSqu)//第二个参数nowK（以后已选整数个数）容易漏写{ //死胡同1 if(nowk == k && sum == x) { if(sumSqu>maxSquare) { maxSquare = sumSqu; st = temp; } return; } //死胡同2 if(index == n || nowk >k || sum>x) ////index==n容易写成index==n-1,第n-1个数是存在的，不能被返回 { return; } //岔路口 temp.push_back(A[index]); DFS(index+1,nowk+1,sum+A[index],sumSqu+A[index]*A[index]); temp.pop_back(); DFS(index+1,nowk,sum,sumSqu);}int main(){ scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d",&A[i]); } scanf("%d",&k); scanf("%d",&x); DFS(0,0,0,0); printf("%d\n",maxSquare); for(int i=0; i<st.size(); i++) { printf("%d ",st[i]); } return 0;}参考书目：《算法笔记》