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:
  1. [
  2.   [3],
  3.   [1],
  4.   [2],
  5.   [1,2,3],
  6.   [1,3],
  7.   [2,3],
  8.   [1,2],
  9.   []
  10. ]

递归

增量构造法

每个元素，都有两种选择，选或者不选。

  1. // Subsets
  2. // 增量构造法，深搜，时间复杂度O(2^n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > subsets(vector<int> &S) {
  6.         sort(S.begin(), S.end());  // 输出要求有序
  7.         vector<vector<int> > result;
  8.         vector<int> path;
  9.         subsets(S, path, 0, result);
  10.         return result;
  11.     }
  13. private:
  14.     static void subsets(const vector<int> &S, vector<int> &path, int step,
  15.             vector<vector<int> > &result) {
  16.         if (step == S.size()) {
  17.             result.push_back(path);
  18.             return;
  19.         }
  20.         // 不选S[step]
  21.         subsets(S, path, step + 1, result);
  22.         // 选S[step]
  23.         path.push_back(S[step]);
  24.         subsets(S, path, step + 1, result);
  25.         path.pop_back();
  26.     }
  27. };

位向量法

开一个位向量bool selected[n]，每个元素可以选或者不选。

  1. // Subsets
  2. // 位向量法，深搜，时间复杂度O(2^n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > subsets(vector<int> &S) {
  6.         sort(S.begin(), S.end());  // 输出要求有序
  8.         vector<vector<int> > result;
  9.         vector<bool> selected(S.size(), false);
  10.         subsets(S, selected, 0, result);
  11.         return result;
  12.     }
  14. private:
  15.     static void subsets(const vector<int> &S, vector<bool> &selected, int step,
  16.             vector<vector<int> > &result) {
  17.         if (step == S.size()) {
  18.             vector<int> subset;
  19.             for (int i = 0; i < S.size(); i++) {
  20.                 if (selected[i]) subset.push_back(S[i]);
  21.             }
  22.             result.push_back(subset);
  23.             return;
  24.         }
  25.         // 不选S[step]
  26.         selected[step] = false;
  27.         subsets(S, selected, step + 1, result);
  28.         // 选S[step]
  29.         selected[step] = true;
  30.         subsets(S, selected, step + 1, result);
  31.     }
  32. };

迭代

增量构造法

  1. // Subsets
  2. // 迭代版，时间复杂度O(2^n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > subsets(vector<int> &S) {
  6.         sort(S.begin(), S.end()); // 输出要求有序
  7.         vector<vector<int> > result(1);
  8.         for (auto elem : S) {
  9.             result.reserve(result.size() * 2);
  10.             auto half = result.begin() + result.size();
  11.             copy(result.begin(), half, back_inserter(result));
  12.             for_each(half, result.end(), [&elem](decltype(result[0]) &e){
  13.                 e.push_back(elem);
  14.             });
  15.         }
  16.         return result;
  17.     }
  18. };

二进制法

本方法的前提是：集合的元素不超过int位数。用一个int整数表示位向量，第i位为1，则表示选择S[i]，为0则不选择。例如 S={A,B,C,D}，则0110=6表示子集 {B,C}。

这种方法最巧妙。因为它不仅能生成子集，还能方便的表示集合的并、交、差等集合运算。设两个集合的位向量分别为B1B_1和B2B_2，则B1∪B2,B1∩B2,B1△B2B_1\cup B_2, B_1 \cap B_2, B_1 \triangle B_2分别对应集合的并、交、对称差。

二进制法，也可以看做是位向量法，只不过更加优化。

  1. // Subsets
  2. // 二进制法，时间复杂度O(2^n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > subsets(vector<int> &S) {
  6.         sort(S.begin(), S.end()); // 输出要求有序
  7.         vector<vector<int> > result;
  8.         const size_t n = S.size();
  9.         vector<int> v;
  11.         for (size_t i = 0; i < 1 << n; i++) {
  12.             for (size_t j = 0; j < n; j++) {
  13.                 if (i & 1 << j) v.push_back(S[j]);
  14.             }
  15.             result.push_back(v);
  16.             v.clear();
  17.         }
  18.         return result;
  19.     }
  20. };

相关题目

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