回溯算法 知识点整理一、回溯算法基础概念1. 什么是回溯算法回溯算法是一种经典的递归搜索算法常用于解决组合问题、排列问题和搜索问题等。2. 基本思想从一个初始状态开始按照一定的规则向前搜索当搜索到某个状态无法前进时回退到前一个状态再按照其他的规则继续搜索。回溯算法在搜索过程中维护一个状态树通过遍历状态树实现对所有可能解的搜索。3. 核心思想“试错”在搜索过程中不断做出选择如果选择正确则继续向前搜索否则回退到上一个状态重新做出选择。回溯算法通常用于解决具有多个解且每个解都需要搜索才能找到的问题。二、回溯算法通用模板Cvoid backtrack(vectorint path, vectorint choices, ...) { // 1. 满足结束条件 if (/* 满足结束条件 */) { // 将路径添加到结果集中 res.push_back(path); return; } // 2. 遍历所有可做的选择 for (int i 0; i choices.size(); i) { // 做出选择 path.push_back(choices[i]); // 做出当前选择后继续递归搜索 backtrack(path, choices); // 撤销选择回溯核心 path.pop_back(); } }关键参数说明path表示当前已经做出的选择即当前的搜索路径。choices表示当前状态下可以做出的所有选择。执行流程做出选择 → 递归搜索 → 撤销选择通过这三步实现状态树的遍历。三、回溯算法复杂度分析时间复杂度通常较高因为需要遍历所有可能的解状态树的所有节点最坏情况下为指数级 O(k^n)k 为每个节点的选择数n 为路径长度。空间复杂度较低因为只需要维护当前状态的路径和递归栈空间复杂度为 O(n)n 为递归深度/路径长度。优化方向实际应用中通常通过剪枝提前排除不可能的分支减少搜索次数提升效率。四、回溯算法的典型应用场景1. 组合问题定义从给定的一组数不重复中选取出所有可能的 k 个数的组合。示例给定数集 [1,2,3]选取 k2 个数的所有组合[1,2]、[1,3]、[2,3]2. 排列问题定义从给定的一组数不重复中选取出所有可能的 k 个数的排列顺序不同视为不同结果。示例给定数集 [1,2,3]选取 k2 个数的所有排列[1,2]、[2,1]、[1,3]、[3,1]、[2,3]、[3,2]3. 子集问题定义从给定的一组数中选取出所有可能的子集包含空集元素顺序不影响。示例给定数集 [1,2,3]所有可能的子集[]、[1]、[2]、[3]、[1,2]、[1,3]、[2,3]、[1,2,3]题目1全排列LeetCode 461. 题目描述给定一个不含重复数字的数组 nums 返回其所有可能的全排列顺序任意。• 示例1输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]• 示例2输入nums [0,1]输出[[0,1],[1,0]]• 示例3输入nums [1]输出[[1]]提示1 nums.length 6-10 nums[i] 10nums中的所有整数互不相同2. 算法思路这是典型的回溯问题核心逻辑是在每一个位置上枚举所有未被使用过的数字放入当前位置递归处理下一个位置当所有位置都处理完成时记录当前排列处理完成后撤销选择枚举其他数字。3. 递归函数设计void backtrack(vectorvectorint res, vectorint nums, vectorbool visited, vectorint ans, int step, int len)参数说明res存储所有合法排列的二维数组。nums输入的不重复数字数组。visited标记数组记录数字是否已被使用避免重复。ans存储当前状态下的排列路径。step当前需要填入数字的位置递归深度。len数组 nums 的长度递归结束条件。函数作用查找所有合法排列并存储到 res 中。4. 递归执行流程1 初始化定义结果集 res、当前路径 ans、标记数组 visited从位置 step0 开始递归。2 递归状态维护用 step 表示当前已处理的数字个数即路径长度。3 结束条件当 step nums.size() 时说明所有位置已填满将 ans 存入 res 并返回。4 遍历与选择对数组的每个下标 i若 visited[i] 为 false未被使用a. 将 visited[i] 标记为 true标记已使用。b. 将 nums[i] 放入 ans[step]做出选择。c. 递归调用 backtrack处理下一个位置 step1。d. 回溯将 visited[i] 重置为 false撤销 ans 中的选择。5 返回结果递归完成后返回 res。5. C 完整代码实现class Solution { public: vectorvectorint ret; // 存储所有排列的结果集 vectorint path; // 存储当前的排列路径 bool check[7]; // 标记数组记录数字是否已被使用nums长度≤6故大小为7 vectorvectorint permute(vectorint nums) { // 初始化标记数组为false所有数字未被使用 memset(check, false, sizeof(check)); dfs(nums); return ret; } void dfs(vectorint nums) { // 递归结束条件路径长度等于数组长度说明找到一个完整排列 if (path.size() nums.size()) { ret.push_back(path); return; } // 遍历所有数字尝试未被使用的数字 for (int i 0; i nums.size(); i) { if (!check[i]) { // 做出选择将nums[i]加入路径标记为已使用 path.push_back(nums[i]); check[i] true; // 递归处理下一个位置 dfs(nums); // 回溯撤销选择恢复现场 path.pop_back(); check[i] false; } } } };6. 回溯算法核心总结1回溯算法的本质是暴力搜索剪枝优化通过递归遍历状态树枚举所有可能的解。2核心流程固定做出选择 → 递归搜索 → 撤销选择通过路径和标记数组维护状态。3典型应用场景组合、排列、子集、N皇后、数独、单词搜索等问题核心都是“枚举剪枝”。4优化关键通过剪枝(如提前排除重复分支、过滤无效路径)降低时间复杂度避免不必要的搜索。题目2子集LeetCode 781. 题目描述给你一个整数数组 nums数组中的元素互不相同。返回该数组所有可能的子集幂集。幂集不能包含重复的子集可以按任意顺序返回解集。• 示例1输入nums [1,2,3]输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]• 示例2输入nums [0]输出[[],[0]]提示1 nums.length 10-10 nums[i] 10nums中的所有元素互不相同2. 算法思路核心逻辑为了获得 nums 数组的所有子集需要对每个元素进行“选”或“不选”的操作因此长度为 n 的数组一定存在 2^n 个子集。回溯核心思想定义一个数组记录当前的状态当前子集并对其进行递归1 对于每个元素有两种选择不选择当前元素直接递归处理下一个元素选择当前元素将其添加到当前子集递归处理下一个元素递归结束后通过回溯撤销添加操作恢复现场。2 递归结束条件当处理的元素下标越界即处理完所有元素时将当前状态子集记录到结果集中并返回。3. 递归函数设计void dfs(vectorvectorint res, vectorint ans, vectorint nums, int step)参数说明res存储所有子集的结果集ans存储当前递归过程中的子集路径nums输入的整数数组step当前需要处理的元素下标递归深度。函数作用递归查找集合的所有子集并存储到结果集中。4. 两种回溯解法解法一“选/不选”分支法二叉树式回溯class Solution { vectorvectorint ret; // 存储所有子集的结果集 vectorint path; // 存储当前递归过程中的子集路径 public: // 入口函数接收数组nums返回所有子集 vectorvectorint subsets(vectorint nums) { dfs(nums, 0); // 从下标0开始递归 return ret; } // 核心回溯函数step表示当前处理的元素下标 void dfs(vectorint nums, int pos) { // 递归结束条件下标越界处理完所有元素 if (pos nums.size()) { ret.push_back(path); // 将当前子集加入结果集 return; } // 分支1选择当前元素nums[pos] path.push_back(nums[pos]); // 做出选择将元素加入路径 dfs(nums, pos 1); // 递归处理下一个元素 path.pop_back(); // 回溯撤销选择恢复现场 // 分支2不选择当前元素nums[pos]直接递归处理下一个元素 dfs(nums, pos 1); } };特点每个元素对应2个分支整体结构是一棵满二叉树递归深度等于数组长度时间复杂度 O(2^n)空间复杂度 O(n)递归栈路径存储。解法二遍历枚举法多叉树式回溯class Solution { vectorvectorint ret; // 存储所有子集的结果集 vectorint path; // 存储当前递归过程中的子集路径 public: // 入口函数接收数组nums返回所有子集 vectorvectorint subsets(vectorint nums) { dfs(nums, 0); // 从下标0开始递归 return ret; } // 核心回溯函数pos表示当前处理的起始下标 void dfs(vectorint nums, int pos) { // 每进入一次递归就将当前路径子集加入结果集 ret.push_back(path); // 从pos开始遍历后续所有元素尝试加入路径 for (int i pos; i nums.size(); i) { path.push_back(nums[i]); // 做出选择将元素加入路径 dfs(nums, i 1); // 递归处理下一个元素避免重复 path.pop_back(); // 回溯撤销选择恢复现场 } } };特点每个节点对应一个子集结构是一棵多叉树递归过程中每一步都记录当前路径无需等到下标越界逻辑更直观时间复杂度 O(2^n)空间复杂度 O(n)。5. 核心知识点总结1 子集问题的本质对每个元素进行“选/不选”的决策所有决策组合构成幂集共 2^n 个子集。2 回溯的核心流程做出选择 → 递归处理 → 撤销选择恢复现场两种解法都遵循这一流程。3 避免重复的关键解法一通过下标递增保证不重复选择同一元素解法二从 pos 开始遍历避免重复枚举相同组合。4 递归结束条件的差异解法一下标越界时记录子集解法二每进入一次递归就记录当前路径无需等待下标越界。
LeetCode回溯算法从入门到精通完整解析
回溯算法 知识点整理一、回溯算法基础概念1. 什么是回溯算法回溯算法是一种经典的递归搜索算法常用于解决组合问题、排列问题和搜索问题等。2. 基本思想从一个初始状态开始按照一定的规则向前搜索当搜索到某个状态无法前进时回退到前一个状态再按照其他的规则继续搜索。回溯算法在搜索过程中维护一个状态树通过遍历状态树实现对所有可能解的搜索。3. 核心思想“试错”在搜索过程中不断做出选择如果选择正确则继续向前搜索否则回退到上一个状态重新做出选择。回溯算法通常用于解决具有多个解且每个解都需要搜索才能找到的问题。二、回溯算法通用模板Cvoid backtrack(vectorint path, vectorint choices, ...) { // 1. 满足结束条件 if (/* 满足结束条件 */) { // 将路径添加到结果集中 res.push_back(path); return; } // 2. 遍历所有可做的选择 for (int i 0; i choices.size(); i) { // 做出选择 path.push_back(choices[i]); // 做出当前选择后继续递归搜索 backtrack(path, choices); // 撤销选择回溯核心 path.pop_back(); } }关键参数说明path表示当前已经做出的选择即当前的搜索路径。choices表示当前状态下可以做出的所有选择。执行流程做出选择 → 递归搜索 → 撤销选择通过这三步实现状态树的遍历。三、回溯算法复杂度分析时间复杂度通常较高因为需要遍历所有可能的解状态树的所有节点最坏情况下为指数级 O(k^n)k 为每个节点的选择数n 为路径长度。空间复杂度较低因为只需要维护当前状态的路径和递归栈空间复杂度为 O(n)n 为递归深度/路径长度。优化方向实际应用中通常通过剪枝提前排除不可能的分支减少搜索次数提升效率。四、回溯算法的典型应用场景1. 组合问题定义从给定的一组数不重复中选取出所有可能的 k 个数的组合。示例给定数集 [1,2,3]选取 k2 个数的所有组合[1,2]、[1,3]、[2,3]2. 排列问题定义从给定的一组数不重复中选取出所有可能的 k 个数的排列顺序不同视为不同结果。示例给定数集 [1,2,3]选取 k2 个数的所有排列[1,2]、[2,1]、[1,3]、[3,1]、[2,3]、[3,2]3. 子集问题定义从给定的一组数中选取出所有可能的子集包含空集元素顺序不影响。示例给定数集 [1,2,3]所有可能的子集[]、[1]、[2]、[3]、[1,2]、[1,3]、[2,3]、[1,2,3]题目1全排列LeetCode 461. 题目描述给定一个不含重复数字的数组 nums 返回其所有可能的全排列顺序任意。• 示例1输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]• 示例2输入nums [0,1]输出[[0,1],[1,0]]• 示例3输入nums [1]输出[[1]]提示1 nums.length 6-10 nums[i] 10nums中的所有整数互不相同2. 算法思路这是典型的回溯问题核心逻辑是在每一个位置上枚举所有未被使用过的数字放入当前位置递归处理下一个位置当所有位置都处理完成时记录当前排列处理完成后撤销选择枚举其他数字。3. 递归函数设计void backtrack(vectorvectorint res, vectorint nums, vectorbool visited, vectorint ans, int step, int len)参数说明res存储所有合法排列的二维数组。nums输入的不重复数字数组。visited标记数组记录数字是否已被使用避免重复。ans存储当前状态下的排列路径。step当前需要填入数字的位置递归深度。len数组 nums 的长度递归结束条件。函数作用查找所有合法排列并存储到 res 中。4. 递归执行流程1 初始化定义结果集 res、当前路径 ans、标记数组 visited从位置 step0 开始递归。2 递归状态维护用 step 表示当前已处理的数字个数即路径长度。3 结束条件当 step nums.size() 时说明所有位置已填满将 ans 存入 res 并返回。4 遍历与选择对数组的每个下标 i若 visited[i] 为 false未被使用a. 将 visited[i] 标记为 true标记已使用。b. 将 nums[i] 放入 ans[step]做出选择。c. 递归调用 backtrack处理下一个位置 step1。d. 回溯将 visited[i] 重置为 false撤销 ans 中的选择。5 返回结果递归完成后返回 res。5. C 完整代码实现class Solution { public: vectorvectorint ret; // 存储所有排列的结果集 vectorint path; // 存储当前的排列路径 bool check[7]; // 标记数组记录数字是否已被使用nums长度≤6故大小为7 vectorvectorint permute(vectorint nums) { // 初始化标记数组为false所有数字未被使用 memset(check, false, sizeof(check)); dfs(nums); return ret; } void dfs(vectorint nums) { // 递归结束条件路径长度等于数组长度说明找到一个完整排列 if (path.size() nums.size()) { ret.push_back(path); return; } // 遍历所有数字尝试未被使用的数字 for (int i 0; i nums.size(); i) { if (!check[i]) { // 做出选择将nums[i]加入路径标记为已使用 path.push_back(nums[i]); check[i] true; // 递归处理下一个位置 dfs(nums); // 回溯撤销选择恢复现场 path.pop_back(); check[i] false; } } } };6. 回溯算法核心总结1回溯算法的本质是暴力搜索剪枝优化通过递归遍历状态树枚举所有可能的解。2核心流程固定做出选择 → 递归搜索 → 撤销选择通过路径和标记数组维护状态。3典型应用场景组合、排列、子集、N皇后、数独、单词搜索等问题核心都是“枚举剪枝”。4优化关键通过剪枝(如提前排除重复分支、过滤无效路径)降低时间复杂度避免不必要的搜索。题目2子集LeetCode 781. 题目描述给你一个整数数组 nums数组中的元素互不相同。返回该数组所有可能的子集幂集。幂集不能包含重复的子集可以按任意顺序返回解集。• 示例1输入nums [1,2,3]输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]• 示例2输入nums [0]输出[[],[0]]提示1 nums.length 10-10 nums[i] 10nums中的所有元素互不相同2. 算法思路核心逻辑为了获得 nums 数组的所有子集需要对每个元素进行“选”或“不选”的操作因此长度为 n 的数组一定存在 2^n 个子集。回溯核心思想定义一个数组记录当前的状态当前子集并对其进行递归1 对于每个元素有两种选择不选择当前元素直接递归处理下一个元素选择当前元素将其添加到当前子集递归处理下一个元素递归结束后通过回溯撤销添加操作恢复现场。2 递归结束条件当处理的元素下标越界即处理完所有元素时将当前状态子集记录到结果集中并返回。3. 递归函数设计void dfs(vectorvectorint res, vectorint ans, vectorint nums, int step)参数说明res存储所有子集的结果集ans存储当前递归过程中的子集路径nums输入的整数数组step当前需要处理的元素下标递归深度。函数作用递归查找集合的所有子集并存储到结果集中。4. 两种回溯解法解法一“选/不选”分支法二叉树式回溯class Solution { vectorvectorint ret; // 存储所有子集的结果集 vectorint path; // 存储当前递归过程中的子集路径 public: // 入口函数接收数组nums返回所有子集 vectorvectorint subsets(vectorint nums) { dfs(nums, 0); // 从下标0开始递归 return ret; } // 核心回溯函数step表示当前处理的元素下标 void dfs(vectorint nums, int pos) { // 递归结束条件下标越界处理完所有元素 if (pos nums.size()) { ret.push_back(path); // 将当前子集加入结果集 return; } // 分支1选择当前元素nums[pos] path.push_back(nums[pos]); // 做出选择将元素加入路径 dfs(nums, pos 1); // 递归处理下一个元素 path.pop_back(); // 回溯撤销选择恢复现场 // 分支2不选择当前元素nums[pos]直接递归处理下一个元素 dfs(nums, pos 1); } };特点每个元素对应2个分支整体结构是一棵满二叉树递归深度等于数组长度时间复杂度 O(2^n)空间复杂度 O(n)递归栈路径存储。解法二遍历枚举法多叉树式回溯class Solution { vectorvectorint ret; // 存储所有子集的结果集 vectorint path; // 存储当前递归过程中的子集路径 public: // 入口函数接收数组nums返回所有子集 vectorvectorint subsets(vectorint nums) { dfs(nums, 0); // 从下标0开始递归 return ret; } // 核心回溯函数pos表示当前处理的起始下标 void dfs(vectorint nums, int pos) { // 每进入一次递归就将当前路径子集加入结果集 ret.push_back(path); // 从pos开始遍历后续所有元素尝试加入路径 for (int i pos; i nums.size(); i) { path.push_back(nums[i]); // 做出选择将元素加入路径 dfs(nums, i 1); // 递归处理下一个元素避免重复 path.pop_back(); // 回溯撤销选择恢复现场 } } };特点每个节点对应一个子集结构是一棵多叉树递归过程中每一步都记录当前路径无需等到下标越界逻辑更直观时间复杂度 O(2^n)空间复杂度 O(n)。5. 核心知识点总结1 子集问题的本质对每个元素进行“选/不选”的决策所有决策组合构成幂集共 2^n 个子集。2 回溯的核心流程做出选择 → 递归处理 → 撤销选择恢复现场两种解法都遵循这一流程。3 避免重复的关键解法一通过下标递增保证不重复选择同一元素解法二从 pos 开始遍历避免重复枚举相同组合。4 递归结束条件的差异解法一下标越界时记录子集解法二每进入一次递归就记录当前路径无需等待下标越界。
