深度优先搜索是递归实现的，是要搜索整个二叉树的，在这个搜索的基础上，再加点回溯/剪枝的操作就是这一类排列组合的题了，是这个关系
- 空间复杂度为O(h)O(h)，对空间复杂度高的考虑DFS
- 不具备最短性
回溯
现实无法回到过去，就在程序回到过去吧！
与动态规划的区别
共同点
- 用于求解多阶段决策问题。多阶段决策问题即：
- 求解一个问题分为很多步骤（阶段）；
- 每一个步骤（阶段）可以有多种选择。
不同点
- 动态规划只需要求我们评估最优解是多少，最优解对应的具体解是什么并不要求。因此很适合应用于评估一个方案的效果；
- 回溯算法可以搜索得到所有的方案（当然包括最优解），但是本质上它是一种遍历算法，时间复杂度很高。
优化
由于回溯算法的时间复杂度很高，因此在遍历的时候，如果能够提前知道这一条分支不能搜索到满意的结果，就可以提前结束，这一步操作称为 剪枝。
排序主要的作用，让程序在深搜的过程中尽量排除掉不能搜索到结果的分支，以节约时间。在回溯搜索这种时间复杂度很大的算法中，先排序再剪枝有些时候是有必要的。
练习
子集
基本思路
注意！！！
变量 t 所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表。
在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，复制的是变量的地址。这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到 66 个空的列表对象。
解决的方法很简单，在 ans.add(new ArrayList<Integer>(t)); 这里做一次拷贝即可。
class Solution {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
dfs(0, nums);
return ans;
}
public void dfs(int cur, int[] nums) {
if (cur == nums.length) {
ans.add(new ArrayList<Integer>(t));
return;
}
t.add(nums[cur]);
dfs(cur + 1, nums);
t.remove(t.size() - 1);
dfs(cur + 1, nums);
}
}
全排列（无重复数据）
题目
分析
可能在这里回想为什么没有出现单体，例如[1]或者[1,2]这种，这里的判断条件和子集那道题不一样，
子集那题的计数，可能在nums.length-1时执行了一次，所以出现只有一个数的数组，执行几次便有几个
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<Integer> List = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
boolean[] st = new boolean[nums.length];
if(nums.length==0)return res;
DFS(nums,res,List,st);
return res;
}
public void DFS(int[] nums, List<List<Integer>> res, List<Integer> List, boolean[] st){
if(List.size() == nums.length){
res.add(new ArrayList<>(List));
return;
}
for(int i = 0; i < nums.length; i ++){
if(!st[i]){
List.add(nums[i]);
st[i]=true;
DFS(nums,res,List,st);
List.remove(List.size()-1);
st[i]=false;
}
}
}
}
基础不牢，多练练这个，注意代码规范
总结：
全排列2(有重复数据)
分析
拿到题目，发现重复元素，便想到重复必有影响，例如两个相同元素交换可能又是一组数据，想到了剪枝
因为全排列，所以数据不够的不会被选中，我们只需要让重复的数据无法继续即可
- 如果这个数和前一个数相同且前一个数还没有用过，continue
- 比如11'2可以，1'12不行，因为1'在1前面使用，1还未使用
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
List<List<Integer>> res = new ArrayList<List<Integer>>();
boolean[] st = new boolean[nums.length];
Arrays.sort(nums);//要去重，故先排序
DFS(nums,list,res,st);
return res;
}
public void DFS(int[] nums, List<Integer> list, List<List<Integer>> res, boolean[] st){
if(list.size()==nums.length){
//注意不要写成List<Integer>
res.add(new ArrayList<>(list));
return;
}
for(int i = 0; i < nums.length; i ++){
if(i>0&&nums[i]==nums[i-1]&&!st[i-1])continue;
if(!st[i]){
list.add(nums[i]);
st[i]=true;
DFS(nums,list,res,st);
list.remove(list.size()-1);
st[i]=false;
}
}
}
}
组合总和
分析
还是全排列，然后将符合的加入，能优化就是剪枝，关键点排序，主要的作用，让程序在深搜的过程中尽量排除掉不能搜索到结果的分支
DFS一般就那几个参数
如果不是全局变量，DFS（答案合集，单个答案，条件，目标，计数）
第一种成员
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<Integer> path = new ArrayList<>();
Arrays.sort(candidates);
backtrack(path,candidates,target,0,0);
return res;
}
public void backtrack(List<Integer> path,int[] candidates, int target, int sum, int begin){
if(sum==target){
res.add(new ArrayList<>(path));
return;
}
for(int i = begin; i < candidates.length; i ++){
int rs = sum + candidates[i];
if(sum<=target){
path.add(candidates[i]);
backtrack(path,candidates,target,rs,i);
path.remove(path.size() - 1);
}else{
break;
}
}
}
}
第二种非成员（推荐）-方法本类就是适用于各种情况
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> combine = new ArrayList<Integer>();
dfs(candidates, target, ans, combine, 0);
return ans;
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
if (idx == candidates.length) {
return;
}
if (target == 0) {
ans.add(new ArrayList<Integer>(combine));
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.add(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.remove(combine.size() - 1);
}
}
}
括号生成
分析
还是全排列的思想，但是有个限制：左右符号都等于n时才算数据，可以采用剪枝（左边大于右边时结束，因为是有效的，必须保证左括号先有）
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
DFS("",0,0,res,n);
return res;
}
public void DFS(String curStr,int left, int right, List<String> res, int n){
if(left==n && right==n){
res.add(curStr);
return;
}
if(left<right)return;
if(left<n){
DFS(curStr+"(",left+1,right,res,n);
}
if(right<n){
DFS(curStr+")",left,right+1,res,n);
}
}
}
寻找重复的子树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
Map<String,TreeNode> coll = new HashMap<String,TreeNode>();
Set<TreeNode> res = new HashSet<TreeNode>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
dfs(root);
return new ArrayList<>(res);
}
public String dfs(TreeNode root){
if(root==null)return "";
StringBuilder sb = new StringBuilder();
sb.append(root.val).append("(");
sb.append(dfs(root.left)).append(")(");
sb.append(dfs(root.right)).append(")");
String serial = sb.toString();
if(coll.containsKey(serial)){
res.add(coll.get(serial));
}else{
coll.put(serial,root);
}
return serial;
}
}
