leetcode-hot100-10回溯

3.回溯

46.全排列

给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

方法一：c

回溯（做选择 -> 递归 -> 撤销选择） = “试探 + 撤销”，深度优先搜索 + 回退,尝试一条路，如果不通，就“退回去”试别的路。

class Solution{public:vector<vector<int>>permute(vector<int>&nums){vector<vector<int>>result;// 结果集：存储所有生成的全排列组合vector<bool>used(nums.size(),false);//标记数组:长度与nums一致，false表示对应位置数字未被使用，true表示已使用vector<int>path;// 路径数组：存储当前递归分支中正在构建的单个排列backtrack(nums,used,path,result);// 调用回溯函数，开始深度优先搜索所有排列可能returnresult;// 返回最终生成的所有全排列结果}// 注意：原代码此处缺少闭合大括号，已补充修正private:// 回溯核心函数：递归遍历所有排列可能，构建并收集全排列//nums:原始输入数组，提供排列的数据源|used:标记数组，记录数字使用状态|path:当前构建的排列路径|result:结果集，收集所有完整排列voidbacktrack(vector<int>&nums,vector<bool>&used,vector<int>&path,vector<vector<int>>&result){if(path.size()==nums.size()){// 递归终止条件：当前路径长度等于原始数组长度，说明已构建出一个完整排列result.push_back(path);// 将当前完整的排列路径添加到结果集中return;// 终止当前递归分支，返回上一层继续探索其他可能}for(inti=0;i<nums.size();++i){// 遍历原始数组中的每一个数字，尝试将其加入当前路径if(used[i])continue;// 剪枝：如果当前数字已被使用（标记为true），则跳过该数字，避免重复选择used[i]=true;// 做出选择：标记当前数字为已使用，防止后续递归重复选取path.push_back(nums[i]);// 做出选择：将当前数字添加到排列路径的末尾，构建当前路径backtrack(nums,used,path,result);// 递归调用：进入下一层递归，继续选择下一个数字构建排列path.pop_back();// 回溯撤销选择：将最后加入的数字从路径中移除，恢复路径状态used[i]=false;// 回溯撤销选择：将当前数字的使用标记重置为false，允许其他分支重新选取}}};

方法一：js

varpermute=function(nums){letresult=[];// 存储最终结果的数组letused=newArray(nums.length).fill(false);// 初始化标记数组letpath=[];// 存储当前路径constbacktrack=()=>{if(path.length===nums.length){// 递归终点result.push([...path]);// 拷贝当前路径并存入结果集return;}for(leti=0;i<nums.length;i++){// 遍历数字if(used[i])continue;// 剪枝：跳过已使用的元素used[i]=true;// 记录当前元素已使用path.push(nums[i]);// 压入路径backtrack();// 递归深搜path.pop();// 回溯：弹出路径末尾元素used[i]=false;// 回溯：释放使用标记}};backtrack();// 开始执行returnresult;// 返回结果};

方法一：java

classSolution{publicList<List<Integer>>permute(int[]nums){List<List<Integer>>res=newArrayList<>();// 结果集boolean[]used=newboolean[nums.length];// 标记数字是否被使用backtrack(nums,used,newArrayList<>(),res);// 开始回溯returnres;}privatevoidbacktrack(int[]nums,boolean[]used,List<Integer>path,List<List<Integer>>res){if(path.size()==nums.length){res.add(newArrayList<>(path));return;}// 路径满则加入结果for(inti=0;i<nums.length;i++){if(used[i])continue;// 已使用则跳过used[i]=true;path.add(nums[i]);// 选择backtrack(nums,used,path,res);// 递归path.remove(path.size()-1);used[i]=false;// 撤销}}}

78.子集

给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

输入：nums=[1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

方法一:c

[]├──[1]│ ├──[1,2]│ │ └──[1,2,3]│ └──[1,3]├──[2]│ └──[2,3]└──[3]

核心逻辑共性：子集问题的回溯无需 “使用标记数组”，通过控制遍历起始索引（i+1）避免重复子集，且每一步递归的路径都是一个有效子集（需即时收集）。

class Solution{public:vector<vector<int>>subsets(vector<int>&nums){vector<vector<int>>result;// 存放所有子集的结果集vector<int>path;// 存储当前递归分支构建的子集backtrack(nums,0,path,result);// 从索引0开始回溯构建子集returnresult;// 返回所有子集}private:// 回溯核心函数：从指定索引index开始构建子集voidbacktrack(vector<int>&nums,intindex,vector<int>&path,vector<vector<int>>&result){result.push_back(path);// 收集当前路径（每个节点都是一个有效子集，包含空集）for(inti=index;i<nums.size();++i){// 从index开始遍历，避免重复子集path.push_back(nums[i]);// 做选择：将当前数字加入当前子集backtrack(nums,i+1,path,result);// 递归下一层，i+1保证子集元素不重复且有序path.pop_back();// 撤销选择：回溯，移除当前加入的数字}}};

方法一：js

varsubsets=function(nums){constresult=[];// 存放所有子集的结果集constpath=[];// 存储当前递归分支构建的子集// 定义回溯函数：从指定索引index开始构建子集constbacktrack=(index)=>{result.push([...path]);// 收集当前路径（浅拷贝避免引用问题）for(leti=index;i<nums.length;i++){// 从index开始遍历，避免重复子集path.push(nums[i]);// 做选择：将当前数字加入当前子集backtrack(i+1);// 递归下一层，i+1保证子集元素不重复且有序path.pop();// 撤销选择：回溯，移除当前加入的数字}};backtrack(0);// 从索引0开始回溯构建子集returnresult;// 返回所有子集};

方法一：java

classSolution{publicList<List<Integer>>subsets(int[]nums){List<List<Integer>>res=newArrayList<>();// 结果集backtrack(nums,0,newArrayList<>(),res);// 从索引0开始回溯returnres;}privatevoidbacktrack(int[]nums,intindex,List<Integer>path,List<List<Integer>>res){res.add(newArrayList<>(path));// 每个路径都是子集，直接收集for(inti=index;i<nums.length;i++){path.add(nums[i]);// 选择backtrack(nums,i+1,path,res);// 递归下一层path.remove(path.size()-1);// 撤销}}}

17.电话号码的字母组合

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

方法一：c

核心逻辑共性：通过索引控制递归层级（处理第 index 位数字），遍历当前数字对应字母→选字母→递归下一位→回溯，最终收集所有完整组合。和上题差不多，形式上会更复杂，因为是字符串，需要额外处理。

class Solution{public:vector<string>letterCombinations(string digits){if(digits.empty(