五、回溯算法-算法总结

五、回溯算法

5.1 背景

回溯法（backtrack）常用于遍历列表所有子集，是 DFS 深度搜索一种，一般用于全排列，穷尽所有可能，遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 O(N!)，它不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

5.2 模板

result = []
func backtrack(选择列表,路径):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(选择列表,路径)撤销选择

核心就是从选择列表里做一个选择，然后一直递归往下搜索答案，如果遇到路径不通，就返回来撤销这次选择。

5.3 集合类

5.3.1 子集

78. 子集

class Solution {public List<List<Integer>> subsets(int[] nums) {// 构建保存结果的ListList<List<Integer>> result = new ArrayList<>();// 用于保存中间结果的ListList<Integer> temp = new ArrayList<>();backTrack(temp, nums, 0, result);return result;}
// nums 给定的集合
// pos 下次添加到集合中的元素位置索引
// subSet 临时结果集合(每次需要复制保存)
// result 最终结果private void backTrack(List<Integer> temp, int[] nums, int pos, List<List<Integer>> result){// 将当前结果直接复制到结果List中result.add(new ArrayList<>(temp));for(int i = pos;i<nums.length;i++){// 选择、处理结果、再撤销选择temp.add(nums[i]); // 确定当前选择backTrack(temp,nums,i+1,result); // 在nums[i]的基础上作出之后的选择temp.remove(temp.size()-1); // 移除当前选择}}
}

5.3.2 子集2

90. 子集 II

class Solution {public List<List<Integer>> subsetsWithDup(int[] nums) {// 创建用于保存结果的ListList<List<Integer>> result = new ArrayList<>();// 创建用于保存中间结果的ListList<Integer> temp = new ArrayList<>();// 排序整数数组Arrays.sort(nums);backTrack(nums, 0, temp,result);return result;}private void backTrack(int[] nums, int pos, List<Integer> temp, List<List<Integer>> result){result.add(new ArrayList(temp));for(int i = pos;i<nums.length;i++){if(i != pos && nums[i-1] == nums[i]){ // 去除后一个重复选择continue;}temp.add(nums[i]); // 作选择backTrack(nums, i+1, temp, result);// 在当前选择下的后续选择temp.remove(temp.size()-1); // 撤销当前选择}}
}

5.4 排列类

5.4.1 全排列

46. 全排列

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();List<Integer> temp = new ArrayList<>();boolean[] isVisited = new boolean[nums.length];permute(nums, isVisited, result, temp);return result;}/**nums: 原始数据isVisited: 保存已访问过的信息result：保存结果temp：保存过程中的中间结果*/private void permute(int[] nums, boolean[] isVisited, List<List<Integer>> result, List<Integer> temp){int l = nums.length;if(temp.size() == l){ // 终止条件result.add(new ArrayList<>(temp)); // 注意此处需使用复制操作的赋值return;}// 遍历可选择的情况for(int i = 0;i<l;i++){// 排除已经选择过的情况if(isVisited[i]){continue; }temp.add(nums[i]); // 选择情况isVisited[i] = true; // 并记录已经访问过permute(nums, isVisited, result, temp);// 撤销当前选择temp.remove(temp.size()-1);isVisited[i] = false; // 并记录未访问过}}
}

5.4.2 全排列2

全排列 II

class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> result = new ArrayList<>();List<Integer> temp = new ArrayList<>();boolean[] isVisited = new boolean[nums.length];// 排序numsArrays.sort(nums);permuteUnique(nums, isVisited, temp, result);return result;}private void permuteUnique(int[] nums, boolean[] isVisited, List<Integer> temp, List<List<Integer>> result){int l = nums.length;if(temp.size() == l){ // 终止条件result.add(new ArrayList<>(temp));return;}for(int i = 0;i<l;i++){// 条件一：访问过// 条件二：重复情况if(isVisited[i]){continue;}// 上一个元素和当前相同，并且没有访问过就跳过if (i != 0 && nums[i] == nums[i-1] && !isVisited[i-1]) {continue;}temp.add(nums[i]); // 做出选择isVisited[i] = true; //设置访问permuteUnique(nums, isVisited, temp, result);temp.remove(temp.size()-1);isVisited[i] = false;}}
}

5.5 组合类

5.5.1 组合总和

39. 组合总和

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();List<Integer> temp = new ArrayList<>();combinationSum(candidates, target, temp, 0, 0, result);return result;}/**candidates: 候选数组target: 目标值temp: 保存过程中的中间结果sum: 记录temp中的数据总和pos: 定位当前情况位置result: 保存结果*/private void combinationSum(int[] candidates, int target, List<Integer> temp, int sum, int pos, List<List<Integer>> result){if(sum == target){ // 终止条件result.add(new ArrayList<>(temp)); // 记录组合结果return;}// 遍历所有情况for(int i = pos;i<candidates.length;i++){if(sum + candidates[i] > target){ // 若超过目标值则去除当前情况continue;}temp.add(candidates[i]); // 做出选择combinationSum(candidates, target, temp, sum+candidates[i], i, result); // 在当前选择的基础上做出下一步选择temp.remove(temp.size()-1); // 剔除当前情况}}
}

5.5.2 电话号码的字母组合

17. 电话号码的字母组合

class Solution {public List<String> letterCombinations(String digits) {if(digits.equals("")){return new ArrayList<>();}// 保存各数字对应的字母集Map<Character, String> map = new HashMap<>();map.put('2',"abc");map.put('3',"def");map.put('4',"ghi");map.put('5',"jkl");map.put('6',"mno");map.put('7',"pqrs");map.put('8',"tuv");map.put('9',"wxyz");List<String> result = new ArrayList<>();letterCombinations(digits, 0, new StringBuffer(), result, map);return result;}/**digits：原数字数组n：指定当前的位置sb: 保存中间结果result: 保存最终的结果map: 数字到字母的映射*/private void letterCombinations(String digits, int pos, StringBuffer sb, List<String> result, Map<Character, String> map){if(pos == digits.length()){ // 终止条件result.add(new String(sb));return;}// 遍历所有情况for(char c:map.get(digits.charAt(pos)).toCharArray()){sb.append(c); // 做出选择letterCombinations(digits, n+1, sb, result, map); // 在当前情况下作下一步选择// 撤销选择sb.deleteCharAt(sb.length()-1);}}
}