回溯法、全排列、子集等

news/2024/5/21 1:39:56

回溯法

感想：回溯算法本质是一个循环，有点像while循环

一些回溯法（递归）的经典应用

1.全排列
2.子集

其实上面两个点，也是对应着高中数学里面的“排列”与“组合”

1.全排列问题

给定一个集合S{a,b,c}，把其中元素按照不同顺序进行排序，eg.“abc”,“bca”,“cab”…全排列的结果为n!个。

基本思想是树（解答树）的遍历，如果是使用dfs（暴搜），那么可以使用递归来写。

在这里插入图片描述

解答树

/*
暴力全排列的思路是:
维护一个path容器，用来装选择好的内容，从集合S中获取元素[i]，然后查询path中是否存在[i]，如果不存在，跳过该元素，遍历下一个，如果[i]在path中不存在，则将[i]放入path中。
不断重复这个过程，使用dfs进行纵向遍历，使用for循环进行横向遍历。
*/
//伪代码
void dfs(int k){//k层数if(k = n) save(path);//保存path，也就是保存一个答案else{//用else省一个return语句for(int i = 0; i < n; i++){if(!check(S[i])){//检查S[i]是否在path中存在state.set(S[i]) = true;//path.add(S[i]);dfs(k+1);//向下遍历state.set(S[i]) = false;//去掉该元素，为下一个元素放置做好准备（元素+状态的还原）path.remove(S[i]);}}}
}
//样例代码见package cjm.recursion.full_permutation;

2.子集

子集问题描述：使用集合S{1,2,3}中的元素构建新的集合，每个元素只能使用一次，元素一样的集合只算一个，eg.{1,2},{2},{1,2,3}…

其实这个子集问题的本质就是高中学到的组合问题，n个元素有几种组合方式，答案数量为C(n,m)；

增量构造法

/*
思路：与全排列的算法框架类似，也是对解答树进行遍历，不过不同点在于每一次遍历时都要将path加入答案集ans{}，而且将S[i]放到前缀后时所需的判断也是不一样的。具体来说，[i]如果不在path中，且前缀+[i]构成的新集合如果不在答案集中，那么可以将[i]放入path中，并进行遍历。
本质还是dfs纵向遍历+for的横向遍历。
*/
void dfs(int k){//y总那边用的是ufor(int i = 0; i < n; i++){if(!check(S[i])){//检查S[i]是否满足条件([i]属于path，path+[i]属于ans)setState(S[i]);//更新状态，包括将元素加入path，更新新集合在ans的存在等等dfs(k+1);//向下遍历reState(S[i]);//恢复状态}}}