• 关键字:搜索、回溯
  • 难度:中
  • 题目大意:给出一个存在重复数字的数集,计算其中数字组成的所有不同的排列。

题目描述

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

For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].

解法

说实话,根据笔者的经验,当看到“给出全部方案”的这种要求的时候,基本上都需要采用回溯的方式遍历每一种可能的情况,这里也是如此。

那么在确定了回溯的基础上,我们该如何遍历所有的方案呢?答案是显然的:

  1. 首先枚举排列第1个位置的数字
  2. 剩下的数字中枚举第2个位置的数字
  3. ……
  4. 枚举最后一个位置的数字(其实这个时候也就剩下一个数字了

这样,无疑会遍历到每一个不同的排列,但是也存在着问题,以样例为例,[1,1,2]这样的排列会被遍历到许多次,这就导致最后输出的答案存在着重复。

那么如何解决这样的重复呢?

我们先看看这样的重复是如何产生的,不难发现,[1,1,2]在之前描述的回溯中会枚举2次。如果不用数值而是用这个数在nums中的下标来表示的话,[1,1,2]被枚举的两次分别是[0,1,2]和[1,0,2],即下标为0的“1”和下标为1的“1”在枚举的过程中被考虑成了两个不同的选择,但是在最后的答案中却没有什么不同

而这样产生的重复也非常好解决,就是对于一个位置的同一个取值,只枚举一次,也就是说如果已经在第1个位置上枚举了“1”这个数字,那么即使之后仍然有“1”的取值,也都跳过不进行枚举。

在实际的实现中,我们不妨这样枚举,即将nums数组排序后,只有nums[i]不等于nums[i+1]时,才将nums[i]视作一种可能的取值,即:

for (int i = 0; i < nums.size(); i++) {
    // 确保在一个位置不会枚举两个相同的数
    if (i == nums.size() - 1 || nums[i] != nums[i + 1]) {

    }
}

这样,就可以保证[1,1,2]在最终的方案中只被计算一次。

特别的,当加入了used[]数组用于判断一个数字是否被使用过之后,由于每次使用的一定是所有相同数字中最右侧的一个,所以对于一个取值,如果它右侧的数字是已经被使用过了的,就同样说明这个数是当前所有相同数字中最右侧的可用的了,即:

for (int i = 0; i < nums.size(); i++) if (!used[i]) {
    // 确保在一个位置不会枚举两个相同的数
    if (i == nums.size() - 1 || nums[i] != nums[i + 1] || used[i + 1]) {

    }
}

在添加了这样的限制之后,这道题目就可以被完美的解决了~

参考代码

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        // 输入是无序的,需要先进行排序
        sort(nums.begin(), nums.end());
        // 一些“全局变量”的声明
        vector<int> current;
        vector<vector<int>> ans;
        vector<bool> used(nums.size(), false);
        // 回溯遍历所有方案
        backtracking(ans, nums, current, used);
        return ans;
    }
    void backtracking(vector<vector<int>>& ans, vector<int>& nums, vector<int>& current, vector<bool>& used) {
        // 判断是否已经得出了一组方案
        if (nums.size() == current.size()) {
            ans.push_back(current);
        }
        else {
            // 依次枚举剩下的没有使用的数字
            for (int i = 0; i < nums.size(); i++) if (!used[i]) {
                // 确保在一个位置不会枚举两个相同的数
                if (i == nums.size() - 1 || nums[i] != nums[i + 1] || used[i + 1]) {
                    // 更新状态值
                    current.push_back(nums[i]);
                    used[i] = true;
                    backtracking(ans, nums, current, used);
                    // 回溯
                    used[i] = false;
                    current.pop_back();
                }
            }
        }
    }
};

登录发表评论 注册

反馈意见