alan23273850 的刷題筆記
a456: 子集合
Tags: bitmask, permutation
出處：https://zerojudge.tw/ShowProblem?problemid=a456
提交：https://zerojudge.tw/Submissions?problemid=a456&account=allllllan123456
問題：給你一個正整數 $N\in[1,15]$，請先由元素少到元素多，再由數字小到數字大的順序依序輸出集合 $\{1,2,\dots,N\}$ 的所有子集合。空集合以 $\{0\}$ 代替。
解法：這題其實只要由小到大對每個可能的子集合大小 m=0, m=1, …, 到 m=$N$ 都呼叫一次 d115 的程式碼即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4int N, m;
5
6void dfs(int index, unsigned choose) {
7 if (__builtin_popcount(choose) == m) {
8 cout << '{'; bool print = false;
9 for (int i=0; choose; i++, choose>>=1)
10 if (choose & 1) {
11 if (print) cout << ',';
12 cout << i+1;
13 print = true;
14 }
15 cout << "}\n";
16 return;
17 }
18 if (index==N) return;
19 dfs(index+1, choose | (1<<index));
20 dfs(index+1, choose);
21}
22
23int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
24 int T; cin >> T;
25 while (T--) { cin >> N;
26 cout << "{0}\n";
27 for (m=1; m<=N; m++)
28 dfs(0,0);
29 cout << '\n';
30 }
31 return 0;
32}