[LeetCode]90.Subsets II

简介:

题目

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

思路

78.Subsets的唯一区别就是添加了两行去重的代码。

代码

    /**------------------------------------
    *   日期:2015-03-01
    *   作者:SJF0115
    *   题目: 90.Subsets II
    *   网址:https://oj.leetcode.com/problems/subsets-ii/
    *   结果:AC
    *   来源:LeetCode
    *   博客:
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        vector<vector<int> > subsetsWithDup(vector<int> &S) {
            int size = S.size();
            vector<vector<int> > result;
            vector<int> path;
            // 排序
            sort(S.begin(),S.end());
            // 空集
            result.push_back(path);
            // 其他子集
            for(int i = 1;i <= size;++i){
                DFS(S,size,i,0,path,result);
            }//for
            return result;
        }
    private:
        // s源数据集 n源数据个数 k子集长度 index为第index个元素 path路径 result最终结果
        void DFS(vector<int> &s,int n,int k,int index,vector<int> &path,vector<vector<int> > &result){
            // 一个子集
            if(path.size() == k){
                result.push_back(path);
                return;
            }//if
            for(int i = index;i < n;++i){
                // 去重
                if(i != index && s[i] == s[i-1]){
                    continue;
                }//if
                path.push_back(s[i]);
                DFS(s,n,k,i+1,path,result);
                path.pop_back();
            }//for
        }
    };

    int main(){
        Solution s;
        vector<int> num = {1,2,2};
        vector<vector<int> > result = s.subsetsWithDup(num);
        // 输出
        for(int i = 0;i < result.size();++i){
            for(int j = 0;j < result[i].size();++j){
                cout<<result[i][j]<<" ";
            }//for
            cout<<endl;
        }//for
        return 0;
    }

运行时间

这里写图片描述

目录
相关文章
LeetCode 90. Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
111 0
LeetCode 90. Subsets II
|
Python
[LeetCode] Subsets
Recursive (Backtracking) This is a typical problem that can be tackled by backtracking. Since backtracking has a more-or-less similar template, so I do not give explanations for this method.
810 0
|
12月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
169 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
130 6
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
282 2
|
12月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
170 3
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口