中等

题目描述

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

来源，leetcode 每日一题 47. 全排列 II

例如：
给定二叉树 [3,9,20,null,null,15,7],

  1. 输入: [1,1,2]
  2. 输出:
  3. [
  4.   [1,1,2],
  5.   [1,2,1],
  6.   [2,1,1]
  7. ]

解题思路

  1. 回溯法：每个位置每个数字都可能出现，但是由于同一个数字不能重复出现，如何判定不能重复出现：使用一个 visited 数组记录一下访问到的数字，同时回溯前要重置一下。
  2. 去重：要保证每次都是从左边第一个未使用过的数字开始使用，则可以保证不会有重复的数组出现。

    代码

    1. class Solution {
    2.  vector<int> visited;
    3. public:
    4.  void dfs(vector<vector<int>>& result, int idx, vector<int>& nums, vector<int>&perms) {
    5.      if (idx == nums.size()) {
    6.          result.emplace_back(perms);
    7.          return;
    8.      }
    9.      for (int i = 0; i < nums.size(); i++) {
    10.          if (visited[i] || (i > 0 && nums[i] == nums[i-1] && !visited[i-1])) {
    11.              continue;
    12.          }
    13.          perms.emplace_back(nums[i]);
    14.          visited[i] = 1;
    15.          dfs(result, idx+1, nums, perms);
    16.          visited[i]=0;
    17.          perms.pop_back();
    18.      }
    19.  }
    20.  vector<vector<int>> permuteUnique(vector<int>& nums) {
    21.      vector<vector<int>> result;
    22.      vector<int> perms;
    23.      visited = vector<int>(nums.size());
    24.      sort(nums.begin(), nums.end());
    25.      dfs(result, 0, nums, perms);
    26.      return result;
    27.  }
    28. };