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:

  1. [
  2.   [2],
  3.   [1],
  4.   [1,2,2],
  5.   [2,2],
  6.   [1,2],
  7.   []
  8. ]

分析

这题有重复元素，但本质上，跟上一题很类似，上一题中元素没有重复，相当于每个元素只能选0或1次，这里扩充到了每个元素可以选0到若干次而已。

递归

增量构造法

  1. // Subsets II
  2. // 增量构造法，版本1，时间复杂度O(2^n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > subsetsWithDup(vector<int> &S) {
  6.         sort(S.begin(), S.end());  // 必须排序
  8.         vector<vector<int> > result;
  9.         vector<int> path;
  11.         dfs(S, S.begin(), path, result);
  12.         return result;
  13.     }
  15. private:
  16.     static void dfs(const vector<int> &S, vector<int>::iterator start,
  17.             vector<int> &path, vector<vector<int> > &result) {
  18.         result.push_back(path);
  20.         for (auto i = start; i < S.end(); i++) {
  21.             if (i != start && *i == *(i-1)) continue;
  22.             path.push_back(*i);
  23.             dfs(S, i + 1, path, result);
  24.             path.pop_back();
  25.         }
  26.     }
  27. };
  1. // Subsets II
  2. // 增量构造法，版本2，时间复杂度O(2^n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > subsetsWithDup(vector<int> &nums) {
  6.         vector<vector<int> > result;
  7.         sort(nums.begin(), nums.end()); // 必须排序
  9.         unordered_map<int, int> count_map; // 记录每个元素的出现次数
  10.         for (int i : nums) {
  11.             if (count_map.find(i) != count_map.end())
  12.                 count_map[i]++;
  13.             else
  14.                 count_map[i] = 1;
  15.         }
  17.         // 将map里的pair拷贝到一个vector里
  18.         vector<pair<int, int> > elems;
  19.         for (auto p : count_map) {
  20.             elems.push_back(p);
  21.         }
  22.         sort(elems.begin(), elems.end());
  23.         vector<int> path; // 中间结果
  25.         dfs(elems, 0, path, result);
  26.         return result;
  27.     }
  29. private:
  30.     static void dfs(const vector<pair<int, int> > &elems,
  31.             size_t step, vector<int> &path, vector<vector<int> > &result) {
  32.         if (step == elems.size()) {
  33.             result.push_back(path);
  34.             return;
  35.         }
  37.         for (int i = 0; i <= elems[step].second; i++) {
  38.             for (int j = 0; j < i; ++j) {
  39.                 path.push_back(elems[step].first);
  40.             }
  41.             dfs(elems, step + 1, path, result);
  42.             for (int j = 0; j < i; ++j) {
  43.                 path.pop_back();
  44.             }
  45.         }
  46.     }
  47. };

位向量法

  1. // Subsets II
  2. // 位向量法，时间复杂度O(2^n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > subsetsWithDup(vector<int> &nums) {
  6.         vector<vector<int> > result; // 必须排序
  7.         sort(nums.begin(), nums.end());
  8.         // 记录每个元素的出现次数
  9.         unordered_map<int, int> count_map;
  10.         for (int i : nums) {
  11.             if (count_map.find(i) != count_map.end())
  12.                 count_map[i]++;
  13.             else
  14.                 count_map[i] = 1;
  15.         }
  16.         // 将map里的pair拷贝到一个vector里
  17.         vector<pair<int, int> > counters;
  18.         for (auto p : count_map) {
  19.             counters.push_back(p);
  20.         }
  21.         sort(counters.begin(), counters.end());
  23.         // 每个元素选择了多少个
  24.         unordered_map<int, int> selected;
  25.         for (auto p : counters) {
  26.             selected[p.first] = 0;
  27.         }
  29.         dfs(nums, counters, selected, 0, result);
  30.         return result;
  31.     }
  33. private:
  34.     static void dfs(const vector<int> &S, const vector<pair<int, int> >& counters,
  35.             unordered_map<int, int>& selected, size_t step, vector<vector<int> > &result) {
  36.         if (step == counters.size()) {
  37.             vector<int> subset;
  38.             for (auto p : counters) {
  39.                 for (int i = 0; i < selected[p.first]; ++i) {
  40.                     subset.push_back(p.first);
  41.                 }
  42.             }
  43.             result.push_back(subset);
  44.             return;
  45.         }
  47.         for (int i = 0; i <= counters[step].second; i++) {
  48.             selected[counters[step].first] = i;
  49.             dfs(S, counters, selected, step + 1, result);
  50.         }
  51.     }
  52. };

迭代

增量构造法

  1. // Subsets II
  2. // 增量构造法
  3. // 时间复杂度O(2^n)，空间复杂度O(1)
  4. class Solution {
  5. public:
  6.     vector<vector<int> > subsetsWithDup(vector<int> &S) {
  7.         sort(S.begin(), S.end()); // 必须排序
  8.         vector<vector<int> > result(1);
  10.         size_t previous_size = 0;
  11.         for (size_t i = 0; i < S.size(); ++i) {
  12.             const size_t size = result.size();
  13.             for (size_t j = 0; j < size; ++j) {
  14.                 if (i == 0 || S[i] != S[i-1] || j >= previous_size) {
  15.                     result.push_back(result[j]);
  16.                     result.back().push_back(S[i]);
  17.                 }
  18.             }
  19.             previous_size = size;
  20.         }
  21.         return result;
  22.     }
  23. };

二进制法

  1. // Subsets II
  2. // 二进制法，时间复杂度O(2^n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > subsetsWithDup(vector<int> &S) {
  6.         sort(S.begin(), S.end()); // 必须排序
  7.         // 用 set 去重，不能用 unordered_set，因为输出要求有序
  8.         set<vector<int> > result;
  9.         const size_t n = S.size();
  10.         vector<int> v;
  12.         for (size_t i = 0; i < 1U << n; ++i) {
  13.             for (size_t j = 0; j < n; ++j) {
  14.                 if (i & 1 << j)
  15.                     v.push_back(S[j]);
  16.             }
  17.             result.insert(v);
  18.             v.clear();
  19.         }
  20.         vector<vector<int> > real_result;
  21.         copy(result.begin(), result.end(), back_inserter(real_result));
  22.         return real_result;
  23.     }
  24. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/brute-force/subsets-ii.html