程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode]90.Subsets II

[LeetCode]90.Subsets II

編輯:C++入門知識

[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 
    #include 
    #include 
    using namespace std;

    class Solution {
    public:
        vector > subsetsWithDup(vector &S) {
            int size = S.size();
            vector > result;
            vector 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 &s,int n,int k,int index,vector &path,vector > &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 num = {1,2,2};
        vector > result = s.subsetsWithDup(num);
        // 輸出
        for(int i = 0;i < result.size();++i){
            for(int j = 0;j < result[i].size();++j){
                cout<

運行時間

這裡寫圖片描述

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved