- dfs模板：
- 216. 组合总和 III （⭐⭐）
- 分析
- 17. 电话号码的字母组合 （⭐⭐⭐）
- 分析
- 131. 分割回文串（⭐⭐⭐）
- 分析
- 40. 组合总和 II （⭐⭐⭐⭐⭐）
- 分析1
- 分析2
下面的几道力扣题均会用到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算法考虑要分四步。
第一步，我需要返回什么，每次遍历出来的值用什么表示，
这道题得返回值是
Listres = new ArrayList<>();
这道题每次遍历的值
LinkedList path = new LinkedList<>();
第二步，确定 dfs中的参数，这里共有四个，分别
n是需要的和，k是所有加起来的数，Index表示开始的至，sum是当前的和。题目说使用数字1-9所以我们从1开始走。
第三步，确定停止条件，当sum的值等于n的值就可以结束，在此有个前提是当我们的元素个数和需要的个数是一样的。
第四步，剪枝条 在dfs的过程中肯定会有大于n的可能，此时需要return，这个操作叫剪枝。
class Solution {
List> result = new ArrayList<>();
LinkedList path = new LinkedList<>();
public List> 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 res = new ArrayList<>();
public List 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
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"]]
回文串 是正着读和反着读都一样的字符串。
分析第一步 确定返回值和遍历值
Listlists = new ArrayList<>();
遍历值
LinkedList path = new LinkedList<>();
第二步 确定dfs中的参数本题只需要字符串s和下标即可
第三步选择结束条件本题的结束条件是 所有子字符串加起来和目标字符串相同。
第四步 剪枝，本题要求是回文字串，对字串是否回文进行判断。
class Solution {
List> res =new ArrayList<>();
LinkedList path = new LinkedList<>();
public List> 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
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
if(s.charAt(i)!=s.charAt(j)){
return false;
}
}
return true;
}
}
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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这里只说这道题的独特之处，建议先刷了这道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> res = new ArrayList<>();
LinkedList path = new LinkedList<>();
public List> 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
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> res = new ArrayList<>();
LinkedList path = new LinkedList<>();
public List> 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();
}
}
}
