dfs(爆搜)

dfs(爆搜) 和 全排列

dfs递归

图解

1. 递归就是把一个大问题变成中问题再变成一个很小的问题进行解决
2. 如果在分解问题时，可能出现一个大问题包括很多个中问题的情况，此时就要在递归外面加上for循环

int n;
int path[N];
int st[N];

void dfs(int u){
    
    if(u>n){
        for(int i=1;i<=n;i++){
            cout << path[i] << " ";
        }
        cout << "\n";
    }
    //空位上可以选择的数字为:1 ~ n
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[u] = i; //此处为u，代表第u个位置需要填
            st[i] = 1;
            
            dfs(u+1);
            /*dfs(u+1)展开： 
            if(u==n){} 
            for(int i=1;i<=n;++){
            	//由于这里有个状态数组，i=1已经被访问过了，所以会把没访问过的 i=2 填入path数组中（真妙！） 
        		if(!state[i]){
					...
					dfs(u+1)
					...
				}
			}
            */
            st[i] = 0;
        }
    }
}

int main(){
    cin >> n;
    dfs(1);
    return 0;
}

next_permutation() 函数

全排列函数 next_permutation(num,num+n) 是对数组num中的前n个元素进行全排列，同时并改变num数组的值。

1. 另外，需要强调的是，next_permutation（）在使用前需要对欲排列数组按升序排序(此时才能找全)，否则只能找出该序列之后的全排列数

2. next_permutation（node,node+n,cmp）可以对结构体num按照自定义的排序方式cmp进行排序

3. 常用方式：

   do{
   
   }while(next_permutation(a,a+n));

dfs例题：
飞机降落问题

使用全排列函数对所有情况进行枚举，判断在所有的情况下是否能够满足条件。
使用方式：

1. 初始化一个全排列数组 a[n] ，通过a[i] = i对其赋值（初始时其为1，2，…,n）
2. 下面每种情况其循环时的下标应当为 a[i]

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

int n,m;
int flag;

struct node{
	int t,d,l;
}p[N];


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> m;
	while(m--){
        cin >> n;
        int a[n]; //全排列数组
        for(int i=1;i<=n;i++) a[i] = i; //初始排列数组为 1,2,3
        for(int i=1;i<=n;i++) cin >> p[i].t >> p[i].d >> p[i].l;
        do{
            //初始化操作
          flag = true;
          int start = 0; // 上一架飞机的降落时间，在此事件后开始降落的飞机都是合法的
          
          //循环某个排序
          for(int i=1;i<=n;i++){
            int j = a[i]; //代表此次排列顺序的下标

            start = max(start , p[j].t) ; // 和飞机到达时间取max,因为有可能上个飞机已经降落完成但下个飞机还没到
            if(p[j].t + p[j].d >= start){
              start += p[j].l;
            }
            else{
              flag = false;
              break;
            }
          }
          
          if(flag){
              //只要有一组排列满足条件即可判定为yes
            cout << "YES" << "\n";
            break;
          }
        }while(next_permutation(a+1,a+n+1));
             
        //只有所有排列都不满足条件才判定为no
        if(!flag) cout << "NO" << "\n";
	}
	return 0;
}

组合问题

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void dfs(int n,int k,int startIndex){
        if(path.size() == k){
            res.push_back(path);
            return;
        }
        else{
            for(int i=startIndex;i<=n;i++){
                path.push_back(i);
                dfs(n,k,i+1);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(n,k,1);
        return res;
    }
};

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

和普通组合问题的区别

1. 组合中的元素个数没有数量要求
2. 元素可无限重复选取

startIndex 不需要在 ++
原始组合问题：backtracking(candidates, target, sum, i+1);
本题的递归回溯：backtracking(candidates, target, sum, i);

在求和问题中，排序之后加剪枝是常见的套路！

排列问题

和组合问题的区别

• 每层都是从0开始搜索而不是startIndex
• 需要used数组记录path里都放了哪些元素了