In tất cả tập con của {1,2,3,…n} không dùng mảng và vòng lặp trong C

Cho số nguyên dương n, in tất cả tập con của tập {1, 2, 3, ..., n} không dùng mảng và vòng lặp (chỉ dùng đệ quy).

Ví dụ n=3 → các tập con: {1 2 3}, {1 2}, {2 3}, {1 3}, {1}, {2}, {3}, { }.

Phương pháp

• Duyệt num từ 2ⁿ - 1 xuống 0.
• Biểu diễn num dưới dạng nhị phân n bit.
• Bit thứ i (từ trái) tương ứng phần tử i+1.
• In các số có bit = 1.
• Lặp cho mọi num.

Mã nguồn C

#include <stdio.h>
#include <math.h>

int subset(int bitn, int num, int num_of_bits) {
    if (bitn >= 0) {
        if ((num & (1 << bitn)) != 0)
            printf("%d ", num_of_bits - bitn);
        subset(bitn - 1, num, num_of_bits);
    } else return 0;
    return 1;
}

int printSubSets(int num_of_bits, int num) {
    if (num >= 0) {
        printf("{ ");
        subset(num_of_bits - 1, num, num_of_bits);
        printf("}");
        printSubSets(num_of_bits, num - 1);
    } else return 0;
    return 1;
}

int main() {
    int n = 4;
    printSubSets(n, (int)(pow(2, n)) - 1);
    return 0;
}

Kết quả

{ 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }