全排列是一道经典的回溯剪枝算法问题给定一个可包含重复数字的序列nums按任意顺序返回所有不重复的全排列。题目要求返回所有不重复的全排列因此需要在排列的基础上进行去重。排列可以采用回溯决策树来进行求解去重则是在回溯的基础上对决策树进行剪枝。整体思路1.排序预处理将数组排序让相同元素相邻。2.回溯搜索构建决策树逐层选择元素。3.剪枝去重在决策树中进行有序选择确保重复元素只以一种固定顺序被选取。例如有三个重复元素a1、a2、a3如果不加剪枝约束那么[a1、a2、a3]和[a2、a1、a3]等排列虽然在数值上完全一样但都会被当做不同的排列生成。剪枝策略要求相同元素在排列中必须按照它们在数组中的顺序出现。即只有前一个相同元素已经被选取时才允许选择当前元素。代码实现class Solution { vectorvectorint res; vectorint path; bool visited[9]; public: vectorvectorint permuteUnique(vectorint nums) { sort(nums.begin(),nums.end()); dfs(nums,0); return res; } void dfs(vectorint nums,int pos) { if(posnums.size()) { res.push_back(path); return; } for(int i0;inums.size();i) { if(visited[i] || ((i!0)(nums[i]nums[i-1]) !visited[i-1])) continue; path.push_back(nums[i]); visited[i]true; dfs(nums,pos1); path.pop_back(); visited[i]false; } } };vectorvectorint resres用于存储所有最终排列结果vectorint pathpath为路径数组用于存储一个正在构建的排列bool visited[9]visited为标记数组用于标记数组中元素是否已被使用res、path、visited均为全局变量。sort(nums.begin(),nums.end())调用sort对数组进行排序让相同元素靠在一起dfs(nums,0)通过dfs递归构建所有排列在每一层递归中通过for循环遍历所有元素if(visited[i] || ((i!0)(nums[i]nums[i-1])!visited[i-1]))通过两个条件进行剪枝visited[i],表示nums[i]已被使用则continue跳过已经被使用的元素(i!0)(nums[i]nums[i-1]!visited[i-1]),nums[i]nums[i-1]遇到重复元素时!visited[i-1]若前一个相同元素没被使用过也continue跳过该元素!visited[i-1]保证了相同数值的元素在排列中必须按照从左往右的固定顺序出现从而完成去重。path.push_back(nums[i])visited[i]true,将nums[i]加入path中并标记为已访问。dfs(nums,pos1),继续向下递归。if(posnums.size())当递归深度达到数组长度时当前路径就是一个完整的排列res.push_back(path)将其加入结果集return;之后进行标准的回溯操作path.pop_back()visited[i]false弹出末尾元素并重置其标志状态为递归其他分支做准备。最终res即为所有去重排列的集合return res即可。全排列这道算法题的核心在于1.通过排序让相同的元素彼此相邻2.剪枝通过固定重复元素的选取顺序避免生成重复排列3.回溯确保能搜索到所有可能的排列组合回溯的核心在于用最简单的递归结构承载了最复杂的决策逻辑而排序、剪枝则是在回溯基础上的进一步优化实现去重。这套方法可以解决包含重复元素的排列组合问题例如字符串排列、子集、组合问题背后的方法都一脉相承掌握排序回溯剪枝这套方法论就能真正实现举一反三