题目大意

解题思路

Code

  1. class Solution {
  2. public:
  3.     vector<vector<int>> ans;
  4.     void dfs(vector<int>& a, int idx, vector<int>& res) {
  5.         if (idx >= a.size()) {
  6.             ans.push_back(res);
  7.             return ;
  8.         }
  9.         dfs(a, idx+1, res);
  10.         res.push_back(a[idx]);
  11.         dfs(a, idx+1, res);
  12.         res.pop_back();
  13.         //ans.push_back(res);
  14.     }
  15.     vector<vector<int>> subsets(vector<int>& nums) {
  16.         vector<int> res(0);
  17.         dfs(nums, 0, res);
  18.         return ans;
  19.     }
  20. };

90
这次数组中有重复元素了，也就导致其子集中会有重复子集。

  • 法0，hash查重，太占空间了
  • 法1，观察规律，发现重复子集是因为，相同元素，上一次没选，而选了这个。排序后使得相同元素相邻！
    class Solution {
public:
  vector<vector<int>> subsetsWithDup(vector<int>& nums) {
      vector<int> res;
      vector<vector<int>> ans;
      unordered_map<vector<int>, int> vis;
      int n = nums.size();
      for (int mask=0;mask<(1<<n);++mask) {
          res.clear();
          for (int i=0;i<n;++i) {
              if (mask&1) {
                  res.push_back(nums[i]);
              }
          }
          if (!vis[res]) {
              ans.push_back(res);
              vis[res] = 1;
          }
      }
      return ans;
  }
};