Subset

• 부분집합 $2^n$

  • Bitmask

    • 부분집합으로 많이 사용
      • 비트마스크 1 << i (i → $2^n$ 까지)
      • 각 마스크(한 조합)별 순회

      •   int total = 1 << n; // 부분집합 개수: 2^n
          for (int mask = 0; mask < total; mask++) {
          	for (int i = 0; i < n; i++) {
          		if (mask & (1 << i)) {
          		}
          	}
          }

    • 부분집합 순회 테크닉
      • mask를 제외한 남은 집합 계산용으로 효율적

      •   int mask = 7;
          int FULL = 1 << 8;
          int rest = ~mask & (FULL - 1);
          for (int subset = rest; subset > 0; subset = (subset - 1) & rest){
              cout << static_cast<bitset<8>>(subset) << endl;
          }

    Link to original

• 부분 집합속 순열
  • DFS
• recursive

  •   #include <iostream>
      #include <vector>
      using namespace std;
      
      void subset(vector<int>& arr, vector<int>& current, int index) {
          if (index == arr.size()) {
              for (int num : current) cout << num << " ";
              cout << "\n";
              return;
          }
      
          // 1. 현재 요소를 포함하는 경우
          current.push_back(arr[index]);
          subset(arr, current, index + 1);
          current.pop_back();
          
          // 2. 현재 요소를 포함하지 않는 경우
          subset(arr, current, index + 1);
      }
      
      int main() {
          vector<int> arr = {1, 2, 3};
          vector<int> current;
          subset(arr, current, 0);
          return 0;
      }

• inductively
  • 1 ~ n

    •   #include <bits/stdc++.h>
        using namespace std;
        
        vector<vector<int>> powerset(int n) {
            // base case: f(0) = { {} }
            if (n == 0) {
                return { {} };
            }
        
            // f(n-1)
            vector<vector<int>> prev = powerset(n - 1);
        
            vector<vector<int>> result = prev;  // f(n-1)
        
            // { A ∪ {n} | A ∈ f(n-1) }
            for (const auto& A : prev) {
                vector<int> with_n = A;
                with_n.push_back(n);
                result.push_back(with_n);
            }
        
            return result;
        }

  • 개별 요소로