DFS，也就是深搜，实质就是枚举。如果题目问的是一共多少种方法,多少种排列...尽管用。
全排列问题：
全排列：给定几个数，要求找出所有的排列方式。
dfs回溯法：
思路：回溯法的核心思路就是模拟过程.下面是全排列问题的伪代码，感受一下
void dfs(int step) {
判断边界；
for(int i=1;i<n;++i ) {// 尝试每一种可能
dfs(step) // 继续下一步
}
返回；
}
举个例子。有A,B,C三个字母需要全排列。可以循环将第一个赋值（A,B,C）,在赋值每个数的时候标记那些用过，那些还能用的数据，执行dfs一直到底层。然后dfs执行完要将数据复原。比如标记的数据进行取消标记等等。
重点是怎么搜，怎么回溯
上代码：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Permutation {
Set<String> result = new HashSet<>();
public String[] permutation(String S) {
char[] sarray = S.toCharArray();
// select 暂存排列的结果，回溯时要恢复
StringBuffer select = new StringBuffer();
// visited
boolean[] visited = new boolean[S.length()];
// 模拟排列的过程，开始挑选元素
pickNext(sarray,select,visited);
String[] resultArray = new String[result.size()];
int index =0;
for(String s:result) {
resultArray[index++] = s;
}
return resultArray;
}
private void pickNext(char[] sarray,StringBuffer select, boolean[] visited) {
// 终止搜索条件，符合条件后，添加到结果集中
if(select.length()== sarray.length) {
System.out.println(select.toString());
result.add(select.toString());
}
// 开搜，for循环中列举所有可能
for(int i=0;i<sarray.length;i++) {
// 已经访问过，不用再添加了
if(visited[i]) {
continue;
}
// 标记访问结果
visited[i]= true;
select.append(sarray[i]);
pickNext(sarray,select,visited);
// 这一步很重要，访问过，回溯回到上一次，把访问标记恢复，继续搜索，
select.delete(select.length()-1,select.length());
visited[i] = false;
}
}
public static void main(String[] args) {
String s = "ABC";
Permutation permutation = new Permutation();
String[] result = permutation.permutation(s);
System.out.println(result.length);
}
}
思想其实很简单，一定要多写几遍，特别回溯是时候，记得要恢复访问的记录~~
分桃子
题目描述下：
现在有n个桃子，分别从中拿出n个桃子，往一些篮子里放。
要求：
每一个篮子里的桃子最少为一个
不能全部放到一个篮子里；
每个篮子的桃子数目不能相同；
不区分篮子的顺序，篮子的数量足够多。
求一共有多少种分发。
输入：桃子的数量N
输出：分发的总数
他不管题目多花哨，都是纸老虎，只是输入不同，输出不同的全排列罢了~~~
上代码：
Set<String> result;
/**
* 分桃子 * * @param n * @return
*/
public int seperate(int n) {
// result 结果集
result = new HashSet<>();
// 暂存已经选择的排列
Set<Integer> selected = new HashSet<>();
for (int i = 1; i < n + 1; i++) {
pickOne(i, n, selected);
}
return result.size();
}
private void pickOne(int i, int remain, Set<Integer> selected) {
// 第一步判断终止条件，不满足条件的结果直接返回
if (remain < 0) {
return;
}
// 满足的结果加入结果集。
// 注意这里有个坑，不能一个篮子里放所有的桃子，selected大小必须大于1
if (remain == 0 && selected.size() > 1) {
Set<Integer> set = new HashSet<>();
set.addAll(selected);
result.add(set.toString());
}
// 模型下一步取桃子的操作
for (int j = 1; j < remain + 1; j++) {
// 判断当前桃子数目是否已经存在
if (!selected.contains(j)) {
selected.add(j);
// 挑选下一个桃子个数，剩余桃子数量变成remain-j
pickOne(j, remain - j, selected);
// 回溯，暂存集里去掉当前
selected.remove(j);
}
}
}
最后看一道LeetCode的题目
分析一波：
题目有了数组，是否可以分割成两个相等的子集。判断是否可以分，也得把子集列出来，能不能找到一个复合条件的。实质还是要找排列。进而，分的两个子集和是可以确定的，都是总和的一半。
上一题是“分桃子”，现在是分两堆总数相等的桃子，是不是很相近呢~
public boolean canPartition(int[] nums) {
Arrays.sort(nums);
int sum = 0;
int length = nums.length;
// 算总数，平均数
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum % 2 == 1) {
return false;
}
int half = sum / 2;
// left,right 是左右两边剩余“桃子”的总数
return dfs(half, half, length-1, nums);
}
private boolean dfs(int left, int right, int index, int[] nums) {
// 终止条件，任意一方不够分
if (left < 0 || right < 0) {
return false;
}
if (left == 0 && right == 0) {
return true;
}
// 模拟取一个数的操作，不是在放左边，就是放右边
// 注意左右两边总数的变化和剩余
return dfs(left-nums[index],right,index-1,nums) || dfs(left,right-nums[index],index-1,nums);
}
PS：打完收工，推荐一个博客《得意忘形》，真是中年危机着的良药。
你的思想是你信息量的集合，用好你的🐧，不要让垃圾🐧占用你的脑子
你的热爱就是你的生命力
不要去焦虑，做好自己的事情，keep trying
做一个手艺人，卖炭翁里“吾亦无他，但手熟尔”
网友评论