全排列Ⅱ-47

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

示例 1：

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 ≤ nums.length ≤ 8
• -10 ≤ nums[i] ≤ 10
• All the integers of nums are unique.

思路

本题可构建一棵求解树，如下图所示：

采用一次DFS即可得到答案。

DFS是基于递归，本题的终止条件是：当前层数等于输入列表的长度时，终止递归。

由于要去重，我们使用STL的set来存放当前路径path。

代码

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector< vector<int> > result;
        if( nums.size() == 0 )   return result;
        if( nums.size() == 1 ) {
            result.push_back( nums );
            return result;
        }
        bool visited[ nums.size() ];
        for(int i = 0; i < nums.size(); i++)
            visited[i] = false;
        vector<int> path;
        set< vector<int> > result_set;
        dfs(nums, 0, result_set, path, visited);
        for(auto it = result_set.begin(); it != result_set.end(); it++)
            result.push_back( *it );
        return result;
    }
    void dfs
    (
        vector<int>& nums,
        int level,
        set< vector<int> >& result_set, 
        vector<int>& path,
        bool visited[]
    ) {
        // 1. Exit condition
        if(level == nums.size()) {
            result_set.insert( path );
            return;
        }
        // 2. Walk every node that not visited
        for(int i = 0; i < nums.size(); i++) {
            int node = nums[i];
            if( !visited[i] ) {
                visited[i] = true;
                path.push_back(node);
                dfs(nums, level+1, result_set, path, visited);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
};