「leetcode」47.全排列 II【回溯算法】详细图解！

解答：

全排列 II 的解法关键在于去重，以下是详细的回溯算法步骤及去重策略：

排序：
- 首先对给定的序列 nums 进行排序。排序是为了便于后续的去重操作，因为相同的数字在排序后会相邻。
回溯算法：
- 使用回溯算法生成全排列。回溯算法通过递归地尝试每一种可能的排列，然后回溯到上一步继续尝试其他可能性。
去重策略：
- 树层去重：在同一树层上，如果前一个数字已经被使用过，并且当前数字与前一个数字相同，则跳过当前数字，以避免生成重复的排列。这可以通过检查 nums[i] 是否等于 nums[i1] 以及 used[i1] 是否为 true 来实现。
- 具体地，在回溯过程中，当递归到第 i 个数字时，如果 i > 0，nums[i] == nums[i1] 且 used[i1] == true，则跳过当前数字 nums[i]。
回溯过程：
- 从第一个数字开始，依次尝试将每个数字加入到当前排列中，并标记为已使用。
- 递归地尝试下一个数字，直到所有数字都被考虑过。
- 在回溯到上一步时，需要将当前数字从排列中移除，并标记为未使用，以便后续尝试其他可能性。
结果存储：
- 当一个完整的排列被生成时，将其加入到结果列表中。

代码实现中的关键点：排序 nums.sort。在回溯过程中，使用 used 数组记录哪些数字已经被使用过。在尝试加入一个数字到当前排列中时，检查去重条件：if i > 0 and nums[i] == nums[i1] and used[i1]。

通过上述步骤和策略，可以高效地生成给定序列的所有不重复全排列。

热门标签