Backtrack - Liệt kê tập con

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