DFS-Recall4

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/permutations-ii/]

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

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

算法描述

​ 这题与之前相比就是可能含有重复元素，所以最重要的是怎样取去重，分析可知，首先将给定的序列进行排序，让后用之前的方法即可，不一样的是需要添加一个判断条件if(i>0&&nums[i]==nums[i-1]&&flag[i]==1)意思是如果当前的位置不是开头，该元素之前的元素值与当前的值相同，并且之前的值已经使用过了，满足这种情况的时候就跳过这次循环；

C++代码

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
class Solution {
public:
    int n;
    vector<bool> flag;
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        flag = vector<bool>(n);
        path = vector<int>(n);
        sort(nums.begin(),nums.end());
        dfs(nums,0,0);
        return ans;
    }
    
    void dfs(vector<int>& nums,int u,int start){
        if(u==n){
            ans.push_back(path);
            return ;
        }
        for(int i=start;i<n;i++){
            if(!flag[i]){
                flag[i] = true;
                path[i]=nums[u];
                dfs(nums,u+1,u+1<n&&nums[u+1]==nums[u]?i+1:0);
                flag[i] = false;
            }
        }
    }
};

Java代码

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
class Solution {
    
    int n;
    int[] flag;
    List<List<Integer>> ans;
    Stack<Integer> path;
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        n = nums.length;
        flag = new int[n];
        ans = new ArrayList<List<Integer>>();
        path = new Stack<Integer>();
        Arrays.sort(nums);
        
        dfs(nums,0);
        
        return ans;
        
    }
    
    public void dfs(int[] nums,int u){
        if(u==n){
            ans.add(new ArrayList<Integer>(path));
            return ;
        }
        for(int i=0;i<n;i++){
            if(flag[i]==0){
                if(i>0&&nums[i]==nums[i-1]&&flag[i-1]==1){
                    continue;
                }
                flag[i] = 1;
                path.push(nums[i]);
                dfs(nums,u+1);
                path.pop();
                flag[i] = 0;
            }
        }
    }
}