Bài toán
In ra tất cả tập con của tập hợp n phần tử {1,2,...,n}
Độ phức tạp
O(n*2^n)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
int n;
bool a[100];
void show() {
for (int i = 1; i <= n; i++)
if (a[i])
printf("%d ", i);
printf("\n");
}
void bt(int u) {
if (u == n + 1) {
show();
return;
}
a[u] = 0;
bt(u + 1);
a[u] = 1;
bt(u + 1);
}
int main() {
scanf("%d", &n);
bt(1);
}
Mô tả
bool a[]
Mảng a chứa n phần tử, a[i]==1 tức là chọn i vào tập con, a[i]==0 ngược lại.
void show()
In ra tập con tương ứng với mảng a[], nói cách khác, in ra các i mà a[i]==1.
void bt(int u)
bt là hàm đệ quy, bt(u) nghĩa là đã xây dựng xong a[1..u-1] (phần a[u..n] chưa được xây dựng), đang xây dựng phần tử a[u].
Nhận xét