算法题-回溯

一、概念1. 什么是回溯回溯 DFS 深度优先搜索 撤销选择形象理解遍历一棵决策树做出选择 → 进入下一层递归递归到底找到答案 / 走不通撤销选择回溯尝试其他分支核心灵魂撤销选择没有撤销就不是回溯2. 回溯适用场景只要题目要求找出所有可行方案、全部组合、全部排列、子集关键词所有、全部、找出所有可能、枚举全部结果二、回溯通用代码模板// 最终结果容器 ListListInteger result new ArrayList(); public void backtrack(参数){ // 【终止条件】收集答案 if(满足条件){ // 重点一定要new新集合引用传递坑 result.add(new ArrayList(path)); return; } // 遍历所有可选元素 for(循环遍历可选元素){ // 【剪枝】过滤无效分支优化可选 if(不符合条件) continue; // 1.选择 path.add(元素); 标记已使用如果需要 // 2.递归 backtrack(更新后的参数); // 3.撤销选择【回溯核心】 path.remove(path.size()-1); 取消标记如果需要 } }2.有序无序代码区分1无序场景组合、子集不区分顺序// 重点i 从 start 开始 for(int i start; i nums.length; i){ path.add(nums[i]); backtrack(..., i 1, path); // 下一轮起点i1不能再选前面的元素 path.remove(path.size()-1); }例子数组 [1,2] 只能生成 [1,2]无法生成 [2,1]2有序场景全排列区分顺序// 重点i 永远从 0 从头遍历 for(int i 0; i nums.length; i){ if(used[i]) continue; // 只禁止同一条路径重复选同一个元素 path.add(nums[i]); used[i] true; backtrack(...); path.remove(path.size()-1); used[i] false; }例子数组 [1,2] 生成 [1,2] 和 [2,1]三、四大经典题型对比面试高频题型 1子集LeetCode 78题目数组找出所有子集[1,2,3]→ [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] ✅特点元素不重复不要求长度每个元素「选 / 不选」两种情况不需要 start 之外的去重不需要 used 数组用 start 控制只向后选取ListListInteger res new ArrayList(); public ListListInteger subsets(int[] nums) { backtrack(nums,0,new ArrayList()); return res; } void backtrack(int[] nums,int start,ListInteger path){ res.add(new ArrayList(path)); for(int istart;inums.length;i){ path.add(nums[i]); backtrack(nums,i1,path); path.remove(path.size()-1); } }题型 2组合LeetCode 77 组合、39 组合总和、40 组合总和 Ⅱ题目给定两个整数n和k返回范围[1, n]中所有可能的k个数的组合。你可以按任何顺序返回答案。示例 1输入n 4, k 2输出[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]ListListInteger res new ArrayList(); public ListListInteger combine(int n, int k) { backtrack(n,k,1,new ArrayList()); return res; } void backtrack(int n,int k,int start,ListInteger path){ if(k 0){ res.add(new ArrayList(path)); return; } //剪枝 i n-k1 for(int istart;in-k1;i){ path.add(i); backtrack(n,k-1,i1,path); path.remove(path.size()-1); } }题型 3全排列LeetCode 46 全排列、47 全排列 Ⅱ题目给定一个不含重复数字的数组nums返回其所有可能的全排列。你可以按任意顺序返回答案。示例 1输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]有顺序ListListInteger res new ArrayList(); public ListListInteger permute(int[] nums) { boolean[] used new boolean[nums.length]; backtrack(nums,used,new ArrayList()); return res; } void backtrack(int[] nums,boolean[] used,ListInteger path){ if(path.size() nums.length){ res.add(new ArrayList(path)); return; } // 遍历所有数字挑选没有用过的数字 for (int i 0; i nums.length; i) { if (used[i]) { continue; // 当前数字已经选过跳过 } // 1.选择把当前数字加入路径标记已使用 path.add(nums[i]); used[i] true; // 2.递归继续选下一个数字 backtrack(nums, path, used); // 3.撤销选择【回溯核心】 path.remove(path.size() - 1); used[i] false; } }题型 4字母组合17. 电话号码字母组合本质是多层循环展开的组合问题每层选对应数字的字符不需要 start、不需要 used。ListString res new ArrayList(); MapCharacter,String map; public ListString letterCombinations(String digits) { if(digits.length()0) return res; 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); backtrack(digits,0,new StringBuffer()); return res; } void backtrack(String digits,int index,StringBuffer sb){ if(index digits.length()){ res.add(sb.toString()); return; } String str map.get(digits.charAt(index)); for(char c : str.toCharArray()){ sb.append(c); backtrack(digits,index1,sb); sb.deleteCharAt(sb.length()-1); } }四、高频区分表重中之重刷题不会混淆题型是否有序核心手段参数特点子集无序start 向后遍历每条路径都收集答案backtrack(...,int start)组合无序start 向后遍历凑够长度收集backtrack(...,int start)全排列有序used 标记数组从头循环backtrack(...,boolean[] used)