Poison

90. Subsets II

发表于
Bit
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 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> resultList = new LinkedList<>();
        Arrays.sort(nums); // 不要忘记排序
        for (int mask = 0; mask < 1 << nums.length; mask++) {
            List<Integer> subList = new LinkedList<>();
            boolean duplicate = false;
            for (int i = 0; i < nums.length; i++) {
                if (((mask >> i) & 1) == 1) {
                    if (i > 0 && nums[i] == nums[i - 1] && ((mask >> (i - 1)) & 1) == 0) {
                        duplicate = true;
                        break;
                    }

                    subList.add(nums[i]);
                }
            }

            if (!duplicate) {
                resultList.add(subList);
            }
        }

        return resultList;
    }
}

去重逻辑分析：
当数组为 [2, 2] 时，我们枚举所有的二进制组合，为了方便演示，右边统一为低位：

1
2
3
4
5
6
index:  1  0
array: [2, 2]
bit:    0  0 -> []
        0  1 -> [2]
        1  0 -> [2]
        1  1 -> [2, 2]

可知子集 [2] 与 [2] 重复，我们只能保留其中一个子集。观察其二进制组合，为 0 1 与 1 0，为了处理方便，我们不保留 1 0 这一种组合。即遍历时，当之前的数字与当前数字相同且前一个数字对应的二进制位为 0 时，我们丢弃该组合。

同理，当数组为 [1, 2, 2] 时，我们枚举所有的二进制组合：

1
2
3
4
5
6
7
8
9
10
index:  2  1  0
array: [2, 2, 1]
bit:    0  0  0 -> []
        0  0  1 -> [1]
        0  1  0 -> [2]
        0  1  1 -> [1, 2]
        1  0  0 -> [2]
        1  0  1 -> [1, 2]
        1  1  0 -> [2, 2]
        1  1  1 -> [1, 2, 2]

可知子集 [2] 与 [2] 重复，二进制组合分别为 0 1 0 与 1 0 0，其中重复的数字 2 对应的二进制组合为 0 1 与 1 0。同上，我们不保留 1 0 0 这一种组合。子集 [1, 2] 与 [1, 2] 重复，二进制组合分别为 0 1 1 与 1 0 1，其中重复的数字 2 对应的二进制组合为 0 1 与 1 0，处理方式同上，我们不保留 1 0 1 这一种组合。

同理，当数组为 [1, 2, 2, 2] 时，我们枚举所有的二进制组合：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
index:  3  2  1  0
array: [2, 2, 2, 1]
bit:    0  0  0  0 -> []
        0  0  0  1 -> [1]
        0  0  1  0 -> [2]
        0  0  1  1 -> [1, 2]
        0  1  0  0 -> [2]
        0  1  0  1 -> [1, 2]
        0  1  1  0 -> [2, 2]
        0  1  1  1 -> [1, 2, 2]
        1  0  0  0 -> [2]
        1  0  0  1 -> [1, 2]
        1  0  1  0 -> [2, 2]
        1  0  1  1 -> [1, 2, 2]
        1  1  0  0 -> [2, 2]
        1  1  0  1 -> [1, 2, 2]
        1  1  1  0 -> [2, 2, 2]
        1  1  1  1 -> [1, 2, 2, 2]

可知子集 [2] 与 [2] 与 [2] 重复，二进制组合分别为 0 0 1 0 与 0 1 0 0 与 1 0 0 0，其中重复的数字 2 对应的二进制组合为 0 0 1 与 0 1 0 与 1 0 0，同上我们不保留 0 1 0 0 与 1 0 0 0 这两种组合。其余重复的子集分析过程同上。

Backtracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        Arrays.sort(nums); // 不要忘记排序
        dfs(resultList, path, nums, 0);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, Deque<Integer> path, int[] nums, int startIndex) {
        resultList.add(new ArrayList<>(path));

        for (int i = startIndex; i < nums.length; i++) {
            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }

            path.add(nums[i]);
            dfs(resultList, path, nums, i + 1);
            path.removeLast();
        }
    }
}
Backtracking
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
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> resultList = new LinkedList<>();
        Deque<Integer> path = new LinkedList<>();
        Arrays.sort(nums);
        dfs(resultList, path, nums, 0, false);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, Deque<Integer> path, int[] nums, int index, boolean preChosen) {
        if (index == nums.length) {
            resultList.add(new ArrayList<>(path));
            return;
        }

        // not choose
        dfs(resultList, path, nums, index + 1, false);

        // 注意此处的过滤条件，仅过滤当前元素与前一个元素值相同且选择当前元素且前一个元素未被选择的情况，即过滤同层中的重复元素
        if (index > 0 && nums[index] == nums[index - 1] && preChosen == false) {
            return;
        }

        // choose
        path.add(nums[index]);
        dfs(resultList, path, nums, index + 1, true);
        path.removeLast();
    }
}

注意过滤条件的位置，仅过滤元素值相同且选择当前元素且未选择前一个元素的场景。即未选择当前元素且未选择前一个元素这种组合不能被过滤。

即对数组 [2, 2] 来说，遍历过程中有四种组合：

2 2
不选 不选
不选 选
选 不选
选 选

其中 [] 组合不能被过滤，即过滤条件一定要写在未选择递归调用之后。

Reference

90. Subsets II