dfs+回溯写题两种思路

本文主要是介绍dfs+回溯写题两种思路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

dfs+回溯写题两种思路

主要框架

	public void dfs(选择列表){//1.找到结束条件//2.遍历所有可能性//2.1做选择//2.2 递归调用自己进一步深度遍历//3.回撤选择
}

• dfs函数的参数变量我觉得是越少越好，所以将一些不怎么改变的变量设置为全局变量更容易理清思路

1.遍历的过程不停的往中间变量添加数据

剑指 Offer 38. 字符串的排列

	static Set<String> res;static char[] ch;static boolean[] ch_helper;public static String[] permutation(String s) {res = new HashSet<>();ch = s.toCharArray();ch_helper = new boolean[ch.length];dfs("");return res.toArray(new String[res.size()]);}private static void dfs(String str) {//1.结束条件if(str.length() == ch.length){res.add(str);}//2.遍历所有可能性for(int i = 0; i < ch.length; i++){if(ch_helper[i] != true){ch_helper[i] = true;dfs(str + ch[i]);ch_helper[i] = false;}}}

46. 全排列

	static List<List<Integer>> res;static LinkedList<Integer> tmp;public static List<List<Integer>> permute(int[] nums) {res = new LinkedList<>();tmp = new LinkedList<>();dfs(nums);return res;}private static void dfs(int[] nums) {if(tmp.size() == nums.length){res.add(new ArrayList<>(tmp));return;}for(int num : nums){if(tmp.contains(num)){continue;}tmp.add(num);dfs(nums);tmp.removeLast();}

2. 遍历的过程改变原列表,这种一般会从下标0开始

剑指 Offer 38. 字符串的排列

static List<String> res;static char[] ch;public static String[] permutation(String s) {res = new LinkedList<>();ch = s.toCharArray();dfs(0);return res.toArray(new String[res.size()]);}private static void dfs(int i) {//1.结束条件if (i == ch.length - 1){res.add(String.valueOf(ch));return;}//2.选择列表Set<Character> set = new HashSet<>();for(int idx = i; idx < ch.length; idx++){if(set.contains(ch[idx]))continue;set.add(ch[idx]);//2.1选择swap(ch, idx, i);//2.2 进一步dfs(i + 1);//3.回溯swap(ch, idx, i);}}private static void swap(char[] ch, int idx, int i) {char tmp = ch[idx];ch[idx] = ch[i];ch[i] = tmp;}

46. 全排列

1. 么有剪枝

static List<String> res;static char[] ch;public static String[] permutation(String s) {res = new LinkedList<>();ch = s.toCharArray();dfs(0);return res.toArray(new String[res.size()]);}private static void dfs(int i) {//1.结束条件if (i == ch.length - 1){res.add(String.valueOf(ch));return;}//2.选择列表for(int idx = i; idx < ch.length; idx++){set.add(ch[idx]);//2.1选择swap(ch, idx, i);//2.2 进一步dfs(i + 1);//3.回溯swap(ch, idx, i);}}private static void swap(char[] ch, int idx, int i) {char tmp = ch[idx];ch[idx] = ch[i];ch[i] = tmp;}

2. 带剪枝

	static List<String> res;static char[] ch;public static String[] permutation(String s) {res = new LinkedList<>();ch = s.toCharArray();dfs(0);return res.toArray(new String[res.size()]);}private static void dfs(int i) {//1.结束条件if (i == ch.length - 1){res.add(String.valueOf(ch));return;}//2.选择列表Set<Character> set = new HashSet<>();for(int idx = i; idx < ch.length; idx++){if(set.contains(ch[idx]))continue;set.add(ch[idx]);//2.1选择swap(ch, idx, i);//2.2 进一步dfs(i + 1);//3.回溯swap(ch, idx, i);}}private static void swap(char[] ch, int idx, int i) {char tmp = ch[idx];ch[idx] = ch[i];ch[i] = tmp;}

这篇关于dfs+回溯写题两种思路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---