1
2
3
4
5

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

1
2

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 回溯法
    pub fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut nums = nums.clone();
        let mut res: Vec<Vec<i32>> = vec![];
        nums.sort();

        /// 回溯
        fn _permute(nums: &[i32], tmp: &[i32], res: &mut Vec<Vec<i32>>) {
            // 终止条件
            if nums.is_empty() {
                res.push(tmp.to_vec());
                return;
            }

            // 遍历
            for (i, &val) in nums.iter().enumerate() {
                if i < 1 || nums[i - 1] != val {
                    let (mut nums_v, mut tmp_v) = (nums.to_vec(), tmp.to_vec());
                    nums_v.remove(i);
                    tmp_v.push(val);
                    //
                    _permute(&nums_v, &tmp_v, res);
                }
            }
        }

        _permute(&nums, &vec![], &mut res);

        res
    }
}
// @lc code=end

struct Solution;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
    vector<vector<int>> result;

public:
    /*
    * ## 解题思路
    * * 回溯法：在46.全排列基础上，增加2个步骤，以处理重复元素；
    * 1. 先对nums进行排序，排序后，重复元素将在nums连续排列；
    * 2. 在递归时，增加重复元素的过滤条件；
    */
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> tmp;            //一次排列
        set<int> visited;           //记录已取元素下标
        sort(nums.begin(), nums.end());
        dfs(nums, tmp, visited);

        return result;
    }

    void dfs(vector<int>&nums, vector<int>& tmp, set<int>& visited) {
        if (tmp.size() == nums.size()) {
            result.push_back(tmp);
            return;
        }
        for(int j=0; j<nums.size(); j++) {
            //跳过已取出的元素
            if (visited.find(j)!=visited.end() || (j>0&&nums[j] == nums[j-1]&&visited.find(j-1)==visited.end())) {
                continue;
            }

            //将未取出的元素取出，加入到tmp中
            tmp.push_back(nums[j]);
            visited.insert(j);  //并记录到visited 集合中；
            //递归处理其他元素
            dfs(nums, tmp, visited);
            //递归返回时，放回已取出的元素
            tmp.pop_back();
            visited.erase(j);
        }
    }
};