【回溯】B009_全排列 II（回溯剪枝 (set 去重 | 判断去重)）

一、题目描述

Given a collection of numbers that might contain duplicates, 
return all possible unique permutations.

Example:
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

二、题解

(1) 回溯剪枝

全排列 $I$I 加剪枝即可：该题是 “全排列” 问题的基础上增加“序列中的元素可重复”这一条件，但要求返回结果不能有重复元素。

去重可用 $set$set；也可另起判断逻辑，后者需让数组 $nums$nums 有序。剪枝条件有二：

• if(isUsed[i]) continue;
• if(i > 0 && nums[i] == nums[i-1] && !isUsed[i-1])
  $\ \ continue;$  continue;
  如果当前元素 $nums[i]$nums[i] 没有被使用过，而且 $nums[i-1]$nums[i−1] 撤回过（$nums[i-1]$nums[i−1] 代表上一次被撤回的元素)，正是因为这些元素，才会产生新的重复的排列。

public List<List<Integer>> permuteUnique(int[] nums) {
  LinkedList<List<Integer>> resList = new LinkedList<>();
  Arrays.sort(nums);
  backtrack(nums, new boolean[nums.length], new ArrayDeque<Integer>(), resList);
  return resList;
}

/**
 * @date: 2/5/2020 12:13 PM
 * @Execution info：ms 击败 % 的j，MB 击败 % 的j
 */
private void backtrack(int[] nums, boolean[] isUsed, Deque<Integer> item, LinkedList<List<Integer>> resList) {
  if(item.size() == nums.length) {
    resList.addLast(new ArrayList<>(item));
    return;
  }

  for (int i = 0; i < nums.length; i++) {
    if(isUsed[i]) 
   	  continue;
    if(i > 0 && nums[i] == nums[i-1] && !isUsed[i-1]) // 把!isUsed[i] 改为 isUsed[i] 慢很多
      continue;

    item.addLast(nums[i]);
    isUsed[i] = true;
    backtrack(nums, isUsed, item, resList);
    item.removeLast();
    isUsed[i] = false;
  }
}

复杂度分析

• 时间复杂度： $O()$O()，
• 空间复杂度：$O()$O()，