47. Permutations II

Leetcode link

解题思路

本题跟 46. Permutations 思路差不多，区别在于这个题目给的数组中有重复项

我们可以在 46 题的基础上，加上两个部分：

• 给 nums 排序，让重复的数字比邻
• 在 46 题的规则上进行剪枝

第一个部分比较好理解，问题在于第二个部分剪枝的规则，我们的思路是：

• 首先我们假设有个重复项 [a~1~, a~2~]，那么我们规定 a~1~ 必须在 a~2~ 前面出现
• 如此一来，我们进行剪枝的规则就出来了：
  1. 判断当前项是否与前一项相等，如果是
  2. 判断前一项是否已经出现了，如果是
  3. 那么不进行剪枝；否则进行剪枝

C++

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<bool> visited(nums.size());

        getPermutations(res, nums, visited, {});
        return res;
    }

    void getPermutations(vector<vector<int>> &res, vector<int>& nums, vector<bool> &visited, vector<int> array) {
        if(array.size() == nums.size()){
            res.push_back(array);
            return;
        }
        for(int i=0;i<nums.size();i++) {
            if(visited[i] || ((i!=0) && (nums[i] == nums[i-1]) && (!visited[i-1]))) {
                continue;
            }
            array.push_back(nums[i]);
            visited[i] = true;
            getPermutations(res, nums, visited, array);
            array.pop_back();
            visited[i] = false;
        }
    }
};

Javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
  // 记得先排序一下让重复项相邻
    nums.sort((a, b)=>a-b);
    let res = [];
    let visited = new Array(nums.length).fill(false);
    getPermutations(res, nums, visited, []);

    return res;
};

var getPermutations = function(res, nums, visited, arr) {
    if(arr.length === nums.length) {
        res.push(arr);
        return;
    }
    for(let i = 0;i<nums.length;i++) {
      // 核心剪枝判断
        if(visited[i] || (i!==0 && nums[i] === nums[i-1] && !visited[i-1])) {
            continue;
        }
        arr.push(nums[i]);
        visited[i] = true;
        getPermutations(res, nums, visited, [...arr]);
        arr.pop();
        visited[i] = false;
    }
}