《挑战程序设计竞赛》—

DFS(深度优先搜索)

简介

深度优先搜索(DFS,Depth-First Search)是搜索的手段之一。它从某个状态开始，不断的转移状态直到无法转移。然后退回到前一步的状态，继续转移到其他状态，如此不断地重复直到找到最后的解。

样例一

题目

部分和问题

给定整数a1,a2----an,判断是否可以从中选出若干数，判断是否存在几个数或某个数和恰为k

分析

对于本题来说只需判断两种状态加与不加，如果此状态满足和为k返回sum==k

代码 O（2 ^n）

//输入

int a[MAX_N];

int n,k;

bool dfs(int i , int sum){

    if (sum == k) return sum == k; //如果和为k返回

    //不加上a[i]

    if(dfs(i+1,sum)) return ture;

    // 加上a[i]

    if(dfs(i+1),sum+a[i]) return ture;

    // 不能凑成k就返回false

    return flase;

}

void solve(){

    if(dfs(0,0)) cout << "Yes" <<endl;

    else cout << "No" ;

}

样例二

Acwing 842. 排列数字

给定一个整数 nn，将数字 1∼n1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 nn。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤71≤n≤7

输入样例：

输出样例：

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10 ;

int path[N]; //表示路径

bool use[N]; // 判断数字是否被用过

int n ;

void dfs(int x)

{

    if (x == n) { //若找到的数字位数等于所需，直接输出结果

        for (int i = 0; i < n; i ++ ) cout << path[i] << " " ;

        cout << endl ;

        return ;

    } 

    for (int i = 1; i <= n; i ++ ) { // 从 i = 1 开始寻找

         if (!use[i]){ //如果i 没有被用过时

             path[x] = i ;  // 将 i 赋给 path

             use[i] = 1 ;   // 标记i被用过了

             dfs(x + 1);    // 寻找下一个数

             use[i] = 0 ;   // 寻找完恢复i

         }

    }

}

int main()

{

    cin >> n;

    dfs(0);

    return 0;

}

巴特西

《挑战程序设计竞赛》——DFS