Cho một tập hợp S, tạo tất cả các tập con riêng biệt của nó, i. e. , tìm tập lũy thừa riêng của tập S. Một tập lũy thừa của bất kỳ tập S nào là tập tất cả các tập con của S, bao gồm tập rỗng và chính S
Ví dụ: nếu S được đặt là {x, y, x}, thì các tập con của S là
- {} [còn được gọi là tập hợp rỗng hoặc tập rỗng]
- {x}
- {y}
- {x}
- {x, y}
- {x, x}
- {y, x}
- {x, y, x}
Do đó, các tập con riêng biệt trong tập lũy thừa của S là. { {}, {x}, {y}, {x, y}, {x, x}, {x, y, x} }
Thực hành vấn đề này
Cách tiếp cận 1. Sử dụng đệ quy
Vấn đề rất giống với vấn đề về chiếc ba lô 0/1, trong đó đối với mỗi phần tử trong tập hợp S, chúng ta có hai lựa chọn
- Xét yếu tố đó
- Đừng xem xét yếu tố đó
Giải pháp sau đây tạo ra tất cả các tổ hợp tập hợp con bằng cách sử dụng logic trên. Để chỉ in các tập hợp con riêng biệt, ban đầu hãy sắp xếp tập hợp con và loại trừ tất cả các phần tử trùng lặp liền kề khỏi tập hợp con cùng với phần tử hiện tại trong trường hợp 2. Điều này được thể hiện dưới đây trong C++, Java và Python
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include
#include
#include
sử dụng không gian tên std;
// Hàm in các phần tử của vector
void printVector[vectơ const &input]
{
cout