回溯小练
下面的几道力扣题均会用到dfs模板，用⭐标记这道题的价值，往往满星是最值得刷的。如果时间来不及刷⭐⭐⭐⭐⭐其他的都是皮毛。
dfs模板：
在dfs模板中for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
第一步需要考虑到东西，返回值res和遍历结果path
dfs(第二步需要考虑的东西){
if(终止条件){}
for（遍历）{
取值
嵌套dfs遍历
//回溯
}}
216. 组合总和 III （⭐⭐）
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
输入: k =3, n =7
输出: [[1,2,4]]
解释:
1 + 2 + 4=7
没有其他符合的组合了。
分析
思路遇到这个题优先考虑dfs算法考虑要分四步。
第一步，我需要返回什么，每次遍历出来的值用什么表示，
这道题得返回值是
List<List> res = new ArrayList<>();
这道题每次遍历的值
LinkedList path = new LinkedList<>();
第二步，确定 dfs中的参数，这里共有四个，分别
n是需要的和，k是所有加起来的数，Index表示开始的至，sum是当前的和。题目说使用数字1-9所以我们从1开始走。
第三步，确定停止条件，当sum的值等于n的值就可以结束，在此有个前提是当我们的元素个数和需要的个数是一样的。
第四步，剪枝条 在dfs的过程中肯定会有大于n的可能，此时需要return，这个操作叫剪枝。
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n){
backTracking(n, k, 1, 0);return result;}
private void backTracking(int targetSum, int k, int startIndex, int sum){
// 减枝
if(sum > targetSum){return;}if(path.size()== k){if(sum == targetSum) result.add(new ArrayList<>(path));return;}for(int i = startIndex; i <=9; i++){
path.add(i);sum+= i;
backTracking(targetSum, k, i + 1, sum);
//回溯
path.removeLast();
//回溯
sum -= i;}}}
17. 电话号码的字母组合 （⭐⭐⭐）
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits ="23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题不用dfs直接遍历也可以。
分析
第一步看返回值 一看就知道这样写把，List < String> list = new ArrayList<>(); 遍历路径一次遍历一个字母。这里需要用到一个字符串数组来表示
String[] numString = {“”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz”}；
第二步 dfs的参数，参数就是 目的 值 还有 字符串数组，还有当前字符串数组的下标。这里用到一个temp来表示每次得到的字符串。
第三步 终止条件当 字符串长度和需求的字符串相同就为终止条件。
第四步 这道题既然可以遍历那么就不需要减枝。
class Solution {
List <String> res = new ArrayList<>();
public List<String> letterCombinations(String digits){
if(digits==null||digits.length()==0){return res;}
String [] nums ={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
dfs(digits,nums,0);return res;}
StringBuilder sb = new StringBuilder();
public void dfs(String digits, String[] nums,int index){
if(sb.length()==digits.length()){
res.add(sb.toString());return;}
String str = nums[digits.charAt(index)-'0'];
for(int i=0;i<str.length();i++){
sb.append(str.charAt(i));
dfs(digits,nums,index+1);
sb.deleteCharAt(sb.length() - 1);}}}
131. 分割回文串（⭐⭐⭐）
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
输入：s ="aab"
输出：[["a","a","b"],["aa","b"]]
回文串 是正着读和反着读都一样的字符串。
分析
第一步 确定返回值和遍历值
List<List> lists = new ArrayList<>();
遍历值
LinkedList path = new LinkedList<>();
第二步 确定dfs中的参数本题只需要字符串s和下标即可
第三步选择结束条件本题的结束条件是 所有子字符串加起来和目标字符串相同。
第四步 剪枝，本题要求是回文字串，对字串是否回文进行判断。
class Solution {
List<List<String>> res =new ArrayList<>();
LinkedList<String> path = new LinkedList<>();
public List<List<String>> partition(String s){
if(s==null||s.length()==0){return res;}
dfs(s,0);return res;}
public void dfs(String s,int index){
if(index >=s.length()){
res.add(new ArrayList(path));return;}
for(int i=index;i<s.length();i++){
if(isTrue(s,index,i)){
String str =s.substring(index,i+1);
path.addLast(str);}else{continue;}
dfs(s,i+1);
path.removeLast();}}
public boolean isTrue(String s,int index,int end){
for(int i =index, j =end;i<j;i++,j--){
if(s.charAt(i)!=s.charAt(j)){returnfalse;}}returntrue;}}
40. 组合总和 II （⭐⭐⭐⭐⭐）
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
输入: candidates =[10,1,2,7,6,1,5], target =8,
输出:
[[1,1,6],
[1,2,5],
[1,7],
[2,6]]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分析1
这里只说这道题的独特之处，建议先刷了这道216. 组合总和 III （⭐⭐）
本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。
做法是通过一个标志位，看是否用过[i-1]这个元素，就好比 一个数组{1，1，2}我们需要得到为3的值，此时举例子有【0，1，0】和【0，0，1】还有【0，1，1】不能重复，我们通过判断 candidates[i]==candidates[i-1]判断 值是重复的按理只能留一个，但是实际会留到【0，1，0】还有【0，1，1】这里离不开判断标志位，
这个!flag[i - 1]=true，表示这层，同一树层candidates[i - 1]使用过。按层来去重就要判断if(i>0&&candidates[i]==candidates[i-1]&& !flag[i - 1])为真。
!flag[i - 1] = false，说明同一树枝candidates[i - 1]使用过。 同一树枝不影响。
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target){
if(target==0){return res;}
boolean[] flag = new boolean[candidates.length];
Arrays.sort(candidates);
dfs(candidates,target,0,0,flag);return res;}
public void dfs(int[] candidates,int target,int index,int sum,boolean[] flag){
if(sum == target){
res.add(new ArrayList <>(path));return;}
for(int i=index ;i<candidates.length;i++){
if(i>0&&candidates[i]==candidates[i-1]&&!flag[i - 1]){continue;}
flag[i]=true;sum=sum + candidates[i];
path.add(candidates[i]);
dfs(candidates,target,i+1,sum,flag);
path.removeLast();
flag[i]=false;sum=sum-candidates[i];}}}
分析2
因为for循环是管树的广度，在广度遍历会出现重复，所以直接跳过广度重复中容易重复的情况。
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum2( int[] candidates, int target ){
//为了将重复的数字都放到一起，所以先进行排序
if(target==0){return res;}
Arrays.sort( candidates );
backTracking( candidates, target, 0 ,0);return res;}
private void backTracking( int[] candidates, int target, int start ,int sum){
if(sum>target){return;}if(sum== target ){
res.add( new ArrayList<>( path ));return;}for( int i = start; i < candidates.length ; i++ ){
//正确剔除重复解的办法
//跳过同一树层使用过的元素
if( i > start && candidates[i]== candidates[i - 1]){continue;}sum+= candidates[i];
path.add( candidates[i]);
// i+1 代表当前组内元素只选取一次
backTracking( candidates, target, i + 1 ,sum);sum=sum-candidates[i];
path.removeLast();}}}
版权归原作者 卷测开的快乐人 所有， 如有侵权，请联系我们删除。