DFS算法专题(三)——综合练习之【经典回溯】
目录
1、电话号码的字母组合
1.1 算法原理
1.2 算法代码
2、括号生成
2.1 算法原理
2.2 算法代码
3、组合
3.1 算法原理
3.2 算法代码
4、目标和
4.1 算法原理
4.2 算法代码【path-->全局变量形式】
4.3 算法代码【path-->dfs参数形式】
5、组合总和
5.1 算法原理【策略一】
5.2 算法代码【策略一】
5.3 算法原理【策略二】
5.4 算法代码【策略二】
1、电话号码的字母组合
. - 力扣（LeetCode）
1.1 算法原理
- 画出决策树，越详细越好
- 设计代码 -> 全局变量: List<String> ret;//返回值 StringBuffer path;//路径 String[] reflect;//digits中元素所映射的字符串
- 设计代码 -> 函数头:dfs(digits, pos); //pos为下一个要添加进path中的digits元素的下标
- 设计代码 -> 函数体 ...
- 设计代码 -> 函数出口:path.length() == digtis.length();
- 设计代码 -> 回溯 -> 恢复现场:path.deleteChatAt(最后一个元素);
- 设计代码 -> 剪枝:无
1.2 算法代码
class Solution {List<String> ret;StringBuffer path;String[] reflect = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {ret = new ArrayList<>();if(digits.equals("")) return ret;path = new StringBuffer();dfs(digits, 0);return ret;}public void dfs(String digits, int pos) {if(path.length() == digits.length()) {ret.add(path.toString());return;}int index = digits.charAt(pos) - '0';for(int i = 0; i < reflect[index].length(); i++) {path.append(reflect[index].charAt(i));dfs(digits, pos + 1);//回溯 -> 恢复现场path.deleteCharAt(path.toString().length()-1);}}
}2、括号生成
. - 力扣（LeetCode）
2.1 算法原理
合法的字符串：
①："(" 的数量始终大于等于 ")" 的数量
②："(" 的个数 <= n
③：最终，( 和 ) 的总数为2n，且各数量相等
代码设计：
- 全局变量：left //记录"("数量；right //记录")"数量；ret //返回值；path //路径
- 函数体：dfs(n)
- 剪枝：当left < n时 -> 可添加"("；当right < left时 -> 可添加")"。
- 回溯(恢复现场)：①：path.delete(最后一个元素)；②：left--/right--;
- 函数出口：left + right == 2*n 或者 right == n
2.2 算法代码
class Solution {List<String> ret;StringBuffer path;int left, right;public List<String> generateParenthesis(int n) {ret = new ArrayList<>();path = new StringBuffer();dfs(n);return ret;}public void dfs(int n) {if ((left + right) == (2 * n)) {ret.add(path.toString());return;}//剪枝if (left < n) {path.append("(");left++;dfs(n);//回溯 -> 恢复现场path.deleteCharAt(path.length() - 1);left--;}//剪枝if(right < left) {path.append(")");right++;dfs(n);//回溯 -> 恢复现场path.deleteCharAt(path.length() - 1);right--;} }
}3、组合
. - 力扣（LeetCode）
3.1 算法原理
- 画决策树
- 设计代码
- 函数头：dfs(n, k)
- 函数体：添加当前元素，接着dfs当前元素的下一层(当前位置的下一个位置)
- 函数出口：path.size()==k
- 回溯：将path恢复现场
- 剪枝：从当前位置的下一个位置开始枚举 --> 自动剪枝
3.2 算法代码
class Solution {List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> combine(int n, int k) {ret = new ArrayList<>();path = new ArrayList<>();dfs(n, k, 1);return ret;}public void dfs(int n, int k, int pos) {//函数出口if (path.size() == k) {ret.add(new ArrayList<>(path));return;}//自动剪枝 -> 从当前元素的下一个位置开始枚举for (int i = pos; i <= n; i++) {path.add(i);dfs(n, k, i + 1);//回溯(恢复现场)path.remove(path.size() - 1);}}
}4、目标和
. - 力扣（LeetCode）
4.1 算法原理
- 决策树
- 设计代码
- 全局变量：ret //返回值；path //记录路径和
- 注意：当path为整形时，也可形参传入(处理简单且函数将自动回溯)。但是全局变量形式和形参形式并无好坏之分，两者均可。
- 函数头：dfs(pos，...)//pos为要进行操作的元素的下标(nums中)
- 函数体：分左右两分支，分别进行nums中元素的加减运算
- 函数出口：pos==nums.length，在出口时判断path是否等于target
- 回溯：恢复path
- 剪枝：无
4.2 算法代码【path-->全局变量形式】
class Solution {int ret;int pathOfSum;public int findTargetSumWays(int[] nums, int target) {dfs(nums, target, 0);return ret;}public void dfs(int[] nums, int target,int pos) {if(pos == nums.length) {if(pathOfSum == target) ret++;return;}//加pathOfSum += nums[pos];dfs(nums, target, pos + 1);//回溯pathOfSum -= nums[pos];//减pathOfSum -= nums[pos];dfs(nums, target, pos + 1);//回溯pathOfSum += nums[pos];}
}4.3 算法代码【path-->dfs参数形式】
class Solution {int ret;public int findTargetSumWays(int[] nums, int target) {dfs(nums, target, 0, 0);return ret;}public void dfs(int[] nums, int target,int pos, int pathOfSum) {if(pos == nums.length) {if(pathOfSum == target) ret++;return;}//加 //参数形式->函数自动回溯dfs(nums, target, pos + 1, pathOfSum + nums[pos]);//减 //参数形式->函数自动回溯dfs(nums, target, pos + 1, pathOfSum - nums[pos]);}
}注意：全局变量形式和形参形式并无好坏之分，两者均可。
5、组合总和
. - 力扣（LeetCode）
5.1 算法原理【策略一】
- 画决策树【决策树并非只有一种！！！】
- 算法思想：DFS回溯搜索即暴力枚举。
注意：为避免结果中数据的重复，每次枚举都应从pos位置开始向后枚举(包含pos位置，因为每一个元素可以重复使用)。
解释：因为2节点得到的[2,3,...]和3节点得到的[3,2,...]的数据组，属于重复枚举，
在选2节点时就已经完成了[2,3,...]的选择，
故在选3节点时，可直接从下一层的3节点处开始选择，即[3,3,...]，
故"每次枚举都应从pos位置开始向后枚举"。
5.2 算法代码【策略一】
class Solution {List<List<Integer>> ret;int sum;List<Integer> path;public List<List<Integer>> combinationSum(int[] candidates, int target) {ret = new ArrayList<>();path = new ArrayList<>();dfs(candidates, target, 0);return ret;}public void dfs(int[] candidates, int target, int pos) {if(sum >= target) {if(sum == target) ret.add(new ArrayList<>(path));return;}for(int i = pos; i < candidates.length; i++) {sum += candidates[i];path.add(candidates[i]);//从当前位置开始枚举(因为一个数据可以多次)，不能枚举前面的元素，否则重复dfs(candidates, target, i);//回溯 -> 清理现场sum -= candidates[i];path.remove(path.size() - 1);}}
}5.3 算法原理【策略二】
- 策略二思想：从一个位置开始枚举，然后1个、2个、....的疯狂枚举，只要 <= target，就继续枚举，当 == target时，就添加这个结果，然后递归下层。
- 细节问题：回溯。注意回溯时，本层数据枚举完成后，再进行恢复现场操作。
5.4 算法代码【策略二】
class Solution {List<List<Integer>> ret;List<Integer> path;int sum;public List<List<Integer>> combinationSum(int[] candidates, int target) {ret = new ArrayList<>();path = new ArrayList<>();dfs(candidates, target, 0);return ret;}public void dfs(int[] candidates, int target, int pos) {if(sum >= target || pos >= candidates.length) {if(sum == target) ret.add(new ArrayList<>(path));return;}for(int k = 0; candidates[pos] * k <= target; k++) {if(k != 0) { path.add(candidates[pos]);sum += candidates[pos];}dfs(candidates, target, pos + 1);}//回溯 -> 恢复现场for(int k = 1; candidates[pos] * k <= target; k++) {sum -= candidates[pos];path.remove(path.size() - 1);}}
}END