前几天在力扣刚刷了集合的问题，今天笔试就遇到了，还是有点差别，没有做出来，太菜了。。。
首先看一下，leetcode 78.子集
问题：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
思路：记原序列中的元素个数为n,序列中的每个元素有两种状态，即在子集中 | 不在子集中，用1，0分别表示在和不在，
则每一个子集就对应一个长度为n的0/1序列。例如：n = 3, a = {1, 2, 3}
| 000 | {} | 0 |
| 001 | {3} | 1 |
| 010 | {2} | 2 |
| 011 | {2, 3} | 3 |
| 100 | {1} | 4 |
| 101 | {1, 3} | 5 |
| 110 | {1, 2} | 6 |
| 111 | {1, 2, 3} | 7 |
可以看到0/1序列对应的二进制正好从0到2n-1, 枚举mask∈[0, 2n-1]，mask的二进制表示是一个 0/1序列，我们可以按照这个 0/1序列在原集合当中取数。当我们枚举完所有mask，就能构造出所有的子集。
复杂度分析
时间复杂度：O(n×2n)，一共 2n个状态，每种状态需要 O(n)的时间来构造子集。
空间复杂度：O(n)。即构造子集使用的临时数组 t的空间代价。
class Solution { public: vector<int> t; vector<vector<int>> res; vector<vector<int>> subsets(vector<int>& nums) { int n=nums.size(); for(int mask = 0; mask < (1<<n); mask++){ t.clear(); for(int i =0; i < n; ++i){ if(mask & (1<<i)){//包含第i位 t.push_back(nums[i]); } } res.push_back(t); } return res; } };
leetcode 90.子集II
问题：
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
思路：
考虑数组 [1,2,2]，选择前两个数，或者第一、三个数，都会得到相同的子集。
也就是说，对于当前选择的数 x，若前面有与其相同的数 y，且没有选择 y，此时包含 x 的子集，必然会出现在包含 y 的所有子集中。
我们可以通过判断这种情况，来避免生成重复的子集。代码实现时，可以先将数组排序；迭代时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。
复杂度分析：
时间复杂度：O(n×2n)，其中 n 是数组 nums 的长度。排序的时间复杂度为O(nlogn)。一共2n个状态，每种状态需要 O(n)的时间来构造子集，一共需要O(n×2n)的时间来构造子集。由于在渐进意义上 O(nlogn) 小于O(n×2n)，故总的时间复杂度为 O(n×2n)。
空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价。
class Solution { public: vector<int> t; vector<vector<int>> ans; vector<vector<int>> subsetsWithDup(vector<int> &nums) { sort(nums.begin(), nums.end()); int n = nums.size(); for (int mask = 0; mask < (1 << n); ++mask) { t.clear(); bool flag = true; for (int i = 0; i < n; ++i) { if (mask & (1 << i)) { if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) { flag = false; break; } t.push_back(nums[i]); } } if (flag) { ans.push_back(t); } } return ans; } };
本次题目：
输入字符串s,，s中可能有重复字母，求s有多少不含重复字母的子序列，相同字母不同下标，视为不同的子序列。
示例输入："aabc"
输出：12
解析："","a","ab","ac","abc","a","ab","ac","abc","b","bc","c"
思路：首先把字符串遍历一遍，记录下每个字符出现的次数，并且把去除重复的字符放入一个字符数组中，然后与子集方法相同，找字符数组的子集，每枚举到一个子集的时候，判断其中的每一个字符是不是重复字符，如果是则count = count + 重复次数。比如aabc ,对于子集"a",包含字符'a'，而‘a’重复的次数为2，故count = count + 2，但是如过没有出现重复，我们就正常+1.
复杂度：
时间复杂度：O(n×2n)，其中遍历去重，记录重复字符，时间复杂度为O(n), 一共2n个状态，每种状态需要 O(n)的时间来构造子集，一共需要O(n×2n)的时间来构造子集。由于在渐进意义上 O(n) 小于O(n×2n)，故总的时间复杂度为 O(n×2n)。
空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价，还有字符数组的代价。
#include<iostream> #include<vector> #include<string> #include<unordered_map> using namespace std; int main(){ string s; cin>>s; unordered_map<int, int> s_map; vector<char> res_str; int i = 0; while(i < s.size()){ if(s_map.find(s[i]) == s_map.end()){ res_str.push_back(s[i]); s_map[s[i]] = 1; }else{ s_map[s[i]]++; } i++; } int level = res_str.size(); int set_count = 1<<level; int count = 0; vector<char> t; for(int i = 0; i < set_count; ++i){ t.clear(); for(int j = 0; j < level; ++j){ if(i & (1 << j)){ t.push_back(res_str[j]); } } if(t.size() > 0){ int sign = 0; for(auto a : t ){ if(s_map[a] > 1){ sign++; count += s_map[a] % 20210101; } } if(sign == 0){ count++; } } else { count++; } } cout<<count; return 0; }