LeetCode:Subsets I II-白红宇

LeetCode:Subsets I II

阅读量：793 次

发布时间：2023-01-31

本文共 2894 字，大约阅读时间需要 9 分钟。

求集合的所有子集问题

求集合的所有子集，需要考虑集合是否有重复元素以及元素的顺序要求。以下是详细的解决方案和分析。

一、给定问题描述

问题要求：

返回集合的所有子集。

子集中的元素必须按非降序排列。

子集不能包含重复项。

例子分析：

对于集合 [1,2,3]，所有子集包括：[ ], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]。

对于集合 [1,2,2]，所有子集包括：[ ], [1], [2], [2] (重复)， [1,2,2], [2,2], [1,2]。

三、解决方案

算法一：DFS方法

代码实现：

#include 
   
    #include 
    
     using namespace std;class Solution {private:    vector
     
      
       > res;public:    vector
       
        
         > subsets(vector
         
           &S) { // 先排序 sort(S.begin(), S.end()); res.clear(); vector
          
            tmpres; dfs(S, 0, tmpres); return res; } void dfs(vector
           
             &S, int iend, vector
            
              &tmpres) { if (iend == S.size()) { res.push_back(tmpres); return; } // 计算当前位置及之前的相同元素数量 int firstSame = iend; while (firstSame >= 0 && S[firstSame] == S[iend]) firstSame--; firstSame++; int sameNum = iend - firstSame; // 检查是否需要新增 // 如果前面没有该元素或者本应有该元素但选的数量不足 if (sameNum == 0 || (tmpres.size() >= sameNum && tmpres[tmpres.size() - sameNum] == S[iend])) { // 选择当前元素 tmpres.push_back(S[iend]); dfs(S, iend + 1, tmpres); tmpres.pop_back(); } // 不选择当前元素 dfs(S, iend + 1, tmpres); }};

算法工作原理：
- 排序：先对集合进行排序，确保子集按非降序生成。
- DFS递归：递归生成所有可能的子集，每次选择或不选择当前元素。
- 去重机制：通过计算前面相同元素的数量，确保不重复生成包含相同元素的子集。

算法二：迭代方法

#include 
    
     #include 
     
      using namespace std;class Solution {private:    vector
      
       
        > res;public:    vector
        
         
          > subsets(vector
          
            &S) { sort(S.begin(), S.end()); res.clear(); vector
           
             empty; res.push_back(empty); int last = S.empty() ? 0 : S[0]; int opResNum = 1; for (int i = 0; i < S.size(); ++i) { if (S[i] != last) { last = S[i]; opResNum = res.size(); } int resSize = res.size(); int opRes = resSize - opResNum; for (int j = opRes; j < resSize; ++j) { res.push_back(res[j]); res.back().push_back(S[i]); } } return res; }};

算法三：二进制方法（适用于无重复元素）

#include 
     
      #include 
      
       using namespace std;class Solution {private:    vector
       
        
         > res;public:    vector
         
          
           > subsets(vector
           
             &S) { sort(S.begin(), S.end()); if (S.empty()) { return { {} }; } res.clear(); res.push_back({}); unsigned long long bit = 1; int len = S.size(); vector
            
              tmp; while (bit <= (1LL << len) - 1) { tmp.clear(); unsigned long long cur = bit; for (int i = 0; i < len; ++i) { if (cur & 1) { tmp.push_back(S[i]); } cur >>= 1; } res.push_back(tmp); bit++; } return res; }};