文章目录
- 全排列 II
- 思路一
全排列 II
给定一个可包含重复数字的序列
nums
,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],[1,2,1],[2,1,1]]示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路一
function permuteUnique(nums) {nums.sort((a, b) => a - b); // 1. 排序以避免重复const results = []; // 存储结果const backtrack = (path, options) => { // 2. 递归函数if (options.length === 0) { // 3. 基本结束条件results.push(path);return;}for (let i = 0; i < options.length; i++) {// 4. 回溯过程: 跳过重复元素if (i > 0 && options[i] === options[i - 1]) continue;const newPath = [...path, options[i]]; // 5.1 添加到路径const newOptions = [...options.slice(0, i), ...options.slice(i + 1)]; // 5.2 移除当前数字backtrack(newPath, newOptions); // 5.3 递归调用}};backtrack([], nums); // 5. 开始回溯return results; // 6. 返回结果
}
讲解
我们需要找到所有不重复的全排列,考虑到序列中可能包含重复的数字,我们需要在递归过程中避免生成重复的排列。
- 排序:首先对输入数组
nums
进行排序。这样可以帮助我们在递归过程中跳过重复的元素。- 递归函数:
○ 定义一个递归函数backtrack
,它接受两个参数:
■path
: 当前正在构建的排列。
■options
: 剩余可选数字的集合。- 基本结束条件:
○ 如果options
集合为空,这意味着我们已经选择了一个全排列。
○ 此时将当前路径path
加入结果数组results
,然后返回。- 回溯过程:
○ 对于options
集合中的每一个数字,执行以下操作:
■ 如果当前数字与前一个数字相同(且前一个数字已经被考虑过),则跳过当前数字以避免重复。
■ 将当前数字添加到路径path
中。
■ 从options
集合中移除当前数字。
■ 递归调用backtrack
函数,传递更新后的path
和options
。
■ 回溯,即将当前数字从路径path
中移除。- 开始回溯:
○ 调用backtrack
函数,传入初始的path
和options
(即nums
)。- 返回结果:
○ 使用一个数组来存储所有不重复的全排列。最后返回结果数组results
。