返回

[Leetcode]90. Subsets II(C++)

题目描述

题目链接:90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

例子

例子 1

Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

Note

The solution set must not contain duplicate subsets.

解题思路

这道题是 [Leetcode]78. Subsets(C++) 的进阶版,要求在输入数组包含重复数字的时候输出的子集组合不能出现重复子集,因此假如输入数组是 [1,1],符合要求的子集组合是 [[], [1], [1,1]]。因此我们需要在前一道题的基础上做法,大致思路包括:

  • 最简单的思路是用一个哈系表存储出现过的子集并自动进行筛选
  • 另一种更好做法是通过剪枝,这样不仅可以筛选所需结果,还能大大降低运行时间,具体做法是:
    • 首先对输入数组进行排序
    • 在 DFS 过程过程添加当前元素时,假如当前索引 i != idx 时并且 nums[i] == nums[i - 1] 时,就表示当前情况已经考虑过了不需要重新进行遍历,因此可以跳过

代码如下:

#include <algorithm>
#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
        std::vector<int> subset;
        std::vector<std::vector<int>> result;

        std::sort(nums.begin(), nums.end());
        dfs(nums, 0, subset, result);
        return result;
    }

private:
    void dfs(const std::vector<int>& nums, size_t idx, std::vector<int>& subset,
             std::vector<std::vector<int>>& result) {
        result.push_back(subset);
        if (idx >= nums.size()) {
            return;
        }

        for (int i = idx; i < nums.size(); ++i) {
            if (i != idx && nums[i] == nums[i - 1]) continue;
            subset.push_back(nums[i]);
            dfs(nums, i + 1, subset, result);
            subset.pop_back();
        }
    }
};
  • 时间复杂度: O(2^n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 90.SubsetsIi.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy