Loading...
墨滴

SuperMP

2021/04/20  阅读:18  主题:默认主题

Leetcode刷题 | 第114题:子集II

为遇一人而入红尘,人去我亦去,此生不留尘。

90. 子集 II

题目:给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。返回的解集中,子集可以按任意顺序排列。

示例 1:
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2:
输入:nums = [0]
输出:[[],[0]]

提示:1 <= nums.length <= 10, -10 <= nums[i] <= 10

分析:相似问题:Leetcode刷题 | 第113题:子集。为了使重复元素相邻,首先对原始数组 nums 排序;其次,考虑一种现象,给定数组 [1,2,4,5,5,6,7],令 index = 3 处的 5 为 index = 4 处的 5 为 ,当使用回溯思想获得每一种可能的子集时:

  1. 若当前递归不选择 index = 3 处的元素,下一递归选择 index = 4 处的元素,那么整个数组(也即从 中)可组合出的的子集集合令为 A;
  2. 若当前递归选择 index = 3 处的元素,下一递归不选择 index = 4 处的元素,那么整个数组(也即从 中)可组合出的的子集集合令为 B;
  3. 有集合 A 完全等同于集合 B,故上述两种状态只需选择一个,以保证在有重复元素出现时,避免子集重复。

Java代码:

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        // pre: 索引idx的上一个索引对应的元素是否被选择
        backtrack(nums, 0false);
        return ans;
    }

    public void backtrack(int[] nums, int idx, boolean pre) {
        if (idx == nums.length) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        backtrack(nums, idx + 1false); // 不选idx处的元素, 并进入idx+1层递归
        if (!pre && idx > 0 && nums[idx - 1] == nums[idx]) // 不再选择idx处的元素, 即时终止
            return;
        temp.add(nums[idx]);
        backtrack(nums, idx + 1true); // 选择idx处的元素, 并进入idx+1层递归
        temp.remove(temp.size() - 1); // 回溯

//        temp.add(nums[idx]);
//        backtrack(nums, idx + 1, true); // 选择idx处的元素, 并进入idx+1层递归
//        temp.remove(temp.size() - 1); // 回溯
//        if (pre && idx > 0 && nums[idx - 1] == nums[idx]) // 不再选择idx处的元素, 即时终止
//            return;
//        backtrack(nums, idx + 1, false); // 不选idx处的元素, 并进入idx+1层递归
    }
}

例如,结合代码和上图可知,当为路线 B 或路线 C 时,会造成其构成的子集为重复子集,故需要丢弃一条:

  • 对于排序的数组,若在递归 index 时,之前递归没有选择 index - 1 处的元素,且有 nums[index] == nums[index - 1],那么递归执行不选择 index 处的元素(路径 D ),不再需要执行选择 index 处的元素(路径 C )。因为,若之前递归选择了 index - 1 处的元素,那么在递归 index 时,可以执行选择 / 不选择 index 处的元素(路径 A / 路径 B )。这样就会保留下路径 ABD,而丢去与路径 B 重复的路径 C。

  • 时间复杂度为 O(N * 2^N),一共有 2^N 个子集状态,且构造每一个子集状态都需要 O(N) 的时间;空间复杂度为 O(N)。

SuperMP

2021/04/20  阅读:18  主题:默认主题

作者介绍

SuperMP