LeetCode/47. 全排列 II

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例 ：

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题的思想就是回溯，也可以说是一种暴力破解方法。我们不断的在递归之前将未出现的元素添加到track数组，在递归之后从track数组剔除元素并尝试加入下一个元素，最终遍历完所有的情况

具体代码如下：

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    //临时结果数组，用于去重
    HashSet<List<Integer>> temRes = new HashSet<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        //记录路径
        LinkedList<Integer> track = new LinkedList<>();
        //标记数组，用于判断当前元素是否已经被遍历过
        boolean[] used = new boolean[nums.length];
        backtrack(nums, track, used);
        //将结果存入res中
        for (List<Integer> temRe : temRes) {
            res.add(temRe);
        }
        return res;
    }

    void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
        //触发结束条件
        if (track.size() == nums.length) {
            temRes.add(new LinkedList<>(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            //排除不合法的选择
            if (used[i]) {
                continue;
            }
          
            //剪枝操作
          	//由于本题会出现重复数字，需要保证重复数组排列只出现一次
          	//通过以下条件，排序后可以保证重复数字按照从左向右的次序依次填入集合
          	//例如：[false, false, false] -> [true, false, false] -> [true, true, false]
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            //将当前元素加入track中并将标记为置为true
            track.add(nums[i]);
            used[i] = true;
            backtrack(nums, track, used);
            //取消选择
            used[i] = false;
            track.removeLast();
        }
    }
}