大家好我是苏麟 , 今天带来几道小题 .

回溯主要解决一些暴力枚举也搞不定的问题，例如组合、分割、子集、排列，棋盘等。这一关我们就看几个例子

回溯热身-再论二叉树路径问题

二叉树的所有路径

描述 :

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

题目 :

LeetCode 257. 二叉树的所有路径 :

二叉树的所有路径

分析 :

这题之前做过解析请看往期 博客
这关用的回溯法解题 , 看懂了LeetCode 77 组合问题的解析 , 这题不在话下

解析 :

/*** 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 {List<String> list = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {dfs(root,new ArrayList<>());return list;}public void dfs(TreeNode root,List<String> temp){if(root == null){return;}temp.add("" + root.val);if(root.left == null && root.right == null){list.add(getString(temp));}dfs(root.left,temp);dfs(root.right,temp);temp.remove(temp.size() - 1);}//结果public String getString(List<String> list){StringBuilder sb = new StringBuilder();sb.append(list.get(0));for(int i = 1;i < list.size();i++){sb.append("->").append(list.get(i));}return sb.toString();}
}

路径总和 II

描述 :

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

题目 :

LeetCode 113. 路径总和 II

路径总和 II

分析 :

往期解析 : 博客
这题也一样 , 懂了回溯法这题也不难

解析 :

/*** 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 {List<List<Integer>> list = new ArrayList<>();LinkedList<Integer> onelist = new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {dfs(root,targetSum);return list;}public void dfs(TreeNode root, int targetSum){if(root == null){return;}targetSum -= root.val;onelist.add(root.val);if(targetSum == 0 && root.left == null && root.right == null){list.add(new LinkedList(onelist));}dfs(root.left,targetSum);dfs(root.right,targetSum);onelist.removeLast();}
}

回溯热门问题

组合总和问题

组合总和

描述 :

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

题目 :

LeetCode 39. 组合总和 :

组合总和

分析 :

如果不考虑重复，本题与LeetCode113题就是一个题，如果可以重复，那是否会无限制取下去呢? 也不会，因为题目给了说明，每个元素最小为1，因此最多也就target个1。

我们画图看该怎么做，对于序列{2,3,6,7}，target=7。很显然我们可以先选择一个2，然后剩下的target就是7-2=5。再选一个2，剩余5-2=3。之后再选一个2，剩余3-2=1。已经小于2了，我们不能继续向下了要返回一下。看看有没有3。OK，序列中有3，那么就得到了第一个结果(2,2,3}。

之后我们继续回退到只选了一个2的时候，这时候不能再取2了，而是从3,6,7)中选择，如下图所示，没有符合要求的!

依次类推，后面尝试从3、6和7开始选择。

所以我们最终得到的结果就是{2,2,3)和 {2,5}。为了方便，我们可以先对元素做个排序，然后将上面的过程画成这个一个树形图:

解析 :

class Solution {List<List<Integer>> list = new ArrayList<>();List<Integer> temp = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {dfs(candidates,0,target);return list;}public void dfs(int[] candidates,int cur, int target){if(target < 0){return;}if(target == 0){list.add(new LinkedList(temp));return;}for(int i = cur;i < candidates.length;i++){if(candidates[i] <= target){temp.add(candidates[i]);dfs(candidates,i,target - candidates[i]);temp.remove(temp.size() - 1);}}}
}

子集问题

子集

描述 :

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

题目 :

LeetCode 78.子集 :

子集

分析 :

我们以[1,2,3] 为例

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。这里什么时候要停下来呢? 其实可以不加终止条件，因为start >= nums.size0，本层for循环本来也结束了。

而且求取子集问题，不需要任何剪枝!因为子集就是要遍历整棵树。这样实现起来也比较容易。

解析 :

class Solution {List<List<Integer>> list = new ArrayList<>();List<Integer> temp = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {dfs(nums,0);return list;}public void dfs(int[] nums , int start){list.add(new ArrayList<>(temp));if(start >= nums.length){return;}for(int i = start;i < nums.length;i++){temp.add(nums[i]);dfs(nums,i + 1);temp.remove(temp.size() - 1);}}
}

这期就到这里下期见!