首页 > 代码库 > LeetCode: Subsets

LeetCode: Subsets

2024-07-20 11:40:15   220人阅读

LeetCode: Subsets

Given a set of distinct integers, 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,3], a solution is:

[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]
地址：https://oj.leetcode.com/problems/subsets/
算法：递归方法。先对数组排序，然后先构造前n-1个数的子集，则n个数的子集就包括两部分，1）前n-1个数子集；2）前n-1个数子集里各元素都加上第n个数。代码：
 1 class Solution { 2 public: 3     vector<vector<int> > subsets(vector<int> &S) { 4         if(S.empty())   return vector<vector<int> >(1,vector<int>()); 5         sort(S.begin(),S.end()); 6         return subsetsCore(S,S.size()); 7     } 8     vector<vector<int> > subsetsCore(vector<int> &S, int n){ 9         vector<vector<int> > result;10         if(n <= 0){11             result.push_back(vector<int>());12             return result;13         }14         vector<vector<int> > temp = subsetsCore(S, n-1);15         result = temp;16         for(int i = 0; i < temp.size(); ++i){17             temp[i].push_back(S[n-1]);18             result.push_back(temp[i]);19         }20         return result;21     }22 };

第二题：

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],  []]
地址：https://oj.leetcode.com/problems/subsets-ii/
算法：数组里有重复的数，要求找出所有的子集。首先还是先对数组进行排序，然后构造只包含第一个元素以及空集这两个子集，然后从第二个数开始循环，若第二个数跟前面的数不一样，则把result里的子集个数加倍，其中多出来的子集为加上第二个数的
子集，若第二个数跟前面的数一样，则在加入新子集时要判断result中是否已经存在该子集。代码：
 1 class Solution { 2 public: 3     vector<vector<int> > subsetsWithDup(vector<int> &S) { 4         vector<vector<int> > result; 5         if(S.empty())   result; 6         sort(S.begin(),S.end()); 7         result.push_back(vector<int>(1,S[0])); 8         result.push_back(vector<int>()); 9         for(int i = 1; i < S.size(); ++i){10             int len = result.size();11             if(S[i] != S[i-1]){12                 for(int j = 0; j < len; ++j){13                     vector<int> temp = result[j];14                     temp.push_back(S[i]);15                     result.push_back(temp);16                 }17             }else{18                 for(int j = 0; j < len; ++j){19                     vector<int> temp = result[j];20                     temp.push_back(S[i]);21                     if(!isExist(result,temp,len)){22                         result.push_back(temp);23                     }24                 }25             }26         }27         return result;28     }29     bool isExist(vector<vector<int> > &result, vector<int> &temp, int len){30         int i = 0;31         while(i < len && !isSameVector(result[i],temp)) ++i;32         return i < len;33     }34     bool isSameVector(const vector<int> v1, const vector<int> v2){35         if(v1.size() != v2.size())36             return false;37         int i = 0;38         while(i < v1.size() && v1[i] == v2[i])  ++i;39         return i == v1.size();40     }41 };

 

LeetCode: Subsets


联系
我们