Leetcode刷题（三十七）

本文主要是介绍Leetcode刷题（三十七），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

全排列II（Medium）

给定一个可包含重复数字的序列 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]]
提示：1 <= nums.length <= 8
-10 <= nums[i] <= 10
Related Topics
数组
回溯

思路分析

全排列问题一般使用递归回溯的方法，由于要排除重复的排列组合，在开始之前，我们先对数组进行排序，这样做的目的是将相同的数字放在一起，便于后续步骤中跳过重复的序列。这里我说一下我设定的变量：
results：存储所有不重复全排列的结果集。
current：当前构建的排列。
nums：给定的数字序列。
used：一个布尔数组，标记每个数字是否已被用于当前排列中。
回溯：在每次递归调用 backtrack 后，我们需要撤销上一步操作，以便回溯到上一个状态并尝试其他可能的数字。这是通过将当前数字从 current 中移除并将 used[i] 标记为未使用来完成的。
根据题意我们可以想到，在排列组合的过程中，每一层数字的确定可以看成从原来的所有数字中，取出一个放置在这一层的位置，依次向下一层放置，这里要注意的是每一层拿出来的数字不能相同，由于数组经过排序，所有重复的元素都是相邻的，只要将这次要拿的元素与本层上一次拿的元素比较是否相同即可。同时拿出的数字不能是之前曾经拿过的，这就是used这个数组的意义所在。
同时，在递归的过程中，如果最后得到的结果等娱乐nums数组的长度，则说明此次递归应该结束了，该返回这次递归的最终结果，回溯到上一层的全排列了。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> results = new ArrayList<>();Arrays.sort(nums); // 排序以方便去重backtrack(results, new ArrayList<>(), nums, new boolean[nums.length]);return results;}private void backtrack(List<List<Integer>> results, List<Integer> current, int[] nums, boolean[] used) {if (current.size() == nums.length) {results.add(new ArrayList<>(current)); // 添加新的排列到结果集return;}for (int i = 0; i < nums.length; i++) {// 如果当前数字已经使用，或者和前一个数字相同但前一个数字还没有使用，跳过if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {continue;}current.add(nums[i]);used[i] = true;backtrack(results, current, nums, used);used[i] = false; // 回溯current.remove(current.size() - 1);}}
}
//leetcode submit region end(Prohibit modification and deletion)