47. 全排列 II

47. 全排列 II

参考剑指 Offer 38. 字符串的排列

问题

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

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,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
# 交换位置，动态维护数组
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(count):
            if count == self.length: 
                res.append(nums.copy())
                return 
            '''
            为了同一个位置避免重复元素，下一次深搜是后一个位置，
            前一个位置的元素记录不影响当前位置，
            此处的引入的visited 对比全排列I，
            在那个问题里用动态维护数组的方法不涉及visited。
            '''
            visited = set() 
            for i in range(count, self.length):
                if nums[i] in visited: continue 
                visited.add(nums[i])
                nums[i], nums[count] = nums[count], nums[i]
                backtrack(count + 1)
                nums[i], nums[count] = nums[count], nums[i]
                visited.remove(nums[i]) # 不需要回溯是因为这里的visited不是
        
        res = []
        self.length = len(nums)
        backtrack(0)
        return res
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
// 一般回溯，visited标记原数组具体位置对应的元素
class Solution {
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
		/*
		这里的perm相当于path，用于记录符合条件的路径。
		用一般回溯算法时，注意两点：
		1. path为引用，
			- 作为dfs参数传入和作为全局变量效果相同；
			- 作为状态变量，dfs完要进行回溯重置；
		2. 添加到res时要添加其拷贝，否则最后的res为null。
		*/
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);	
        }
    }
}