算法——全排列及其他常见DFS问题

全排列

问题描述：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc, acb, bac, bca, cab 和 cba。

思路：回溯

这是一个典型的DFS回溯的算法 回溯法本质是一个基于DFS的穷举的过程

先添加值在判定现有结果是否满足条件DFS回退

代码：

import java.util.ArrayList; import java.util.Collections; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> list=new ArrayList<>(); if(str!=null&&str.length()>0){ PermutationHelp(str.toCharArray(),0,list); Collections.sort(list); } return list; } void PermutationHelp(char[] str,int start,ArrayList<String> list){ if(start == str.length-1){ if(!isHave(str,list)){ list.add(new String(str)); } return; } for(int i=start;i<str.length;i++){ swap(str,i,start); PermutationHelp(str,start+1,list); swap(str,i,start); } } void swap(char[] str,int i,int j){ char temp = str[i]; str[i] = str[j]; str[j] = temp; } boolean isHave(char[] str,ArrayList<String> list){ return list.contains(String.valueOf(str)); } }

二叉树和为某一值的路径

问题描述：

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

来源：牛客链接

代码：

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> list = new ArrayList<>(); FindPathDFS(root, target, lists, list); return lists; } //基于DFS的回溯算法 public void FindPathDFS(TreeNode root, int target, ArrayList<ArrayList<Integer>> lists, ArrayList<Integer> list) { if (root == null) { return; } //将当前值放入list待选结果集中 list.add(root.val); //更新目标值 target -= root.val; // 1. 已经是叶子节点了 // 2. 从root到该叶子节点，之和是target // 3. 是叶子节点，但是不满足节点，也不影响，程序会直接退出 if (root.left == null && root.right == null && target == 0) { //回溯剪枝，去掉不满足条件的 结果 lists.add(new ArrayList<Integer>(list)); //注意深浅拷贝 } FindPathDFS(root.left, target, lists, list); //DFS递归统计 FindPathDFS(root.right, target, lists, list); list.remove(list.size() - 1); }