企业官网建设流程全解析

一、概念

1. 什么是回溯

回溯 = DFS 深度优先搜索 + 撤销选择形象理解：遍历一棵决策树

1. 做出选择 → 进入下一层递归
2. 递归到底（找到答案 / 走不通）
3. 撤销选择（回溯），尝试其他分支

核心灵魂：撤销选择，没有撤销就不是回溯！

2. 回溯适用场景

只要题目要求：找出所有可行方案、全部组合、全部排列、子集

关键词：所有、全部、找出所有可能、枚举全部结果

二、回溯通用代码模板

// 最终结果容器 List<List<Integer>> 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); // 下一轮起点=i+1，不能再选前面的元素 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] ✅特点：

1. 元素不重复，不要求长度
2. 每个元素「选 / 不选」两种情况
3. 不需要 start 之外的去重
4. 不需要 used 数组，用 start 控制只向后选取

List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { backtrack(nums,0,new ArrayList<>()); return res; } void backtrack(int[] nums,int start,List<Integer> path){ res.add(new ArrayList<>(path)); for(int i=start;i<nums.length;i++){ path.add(nums[i]); backtrack(nums,i+1,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], ]

List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { backtrack(n,k,1,new ArrayList<>()); return res; } void backtrack(int n,int k,int start,List<Integer> path){ if(k == 0){ res.add(new ArrayList<>(path)); return; } //剪枝 i <= n-k+1 for(int i=start;i<=n-k+1;i++){ path.add(i); backtrack(n,k-1,i+1,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]（有顺序）

List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { boolean[] used = new boolean[nums.length]; backtrack(nums,used,new ArrayList<>()); return res; } void backtrack(int[] nums,boolean[] used,List<Integer> 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。

List<String> res = new ArrayList<>(); Map<Character,String> map; public List<String> 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,index+1,sb); sb.deleteCharAt(sb.length()-1); } }

四、高频区分表（重中之重，刷题不会混淆）