Sinh tất cả chuỗi con hoán vị từ chuỗi cho trước trong C++

Sinh tất cả chuỗi mọi độ dài từ chuỗi cho trước: tổ hợp chữ số + hoán vị từng tổ hợp.

Ví dụ "ABC"

A, B, C, AB, BA, AC, CA, BC, CB, ABC, ACB, BAC, BCA, CAB, CBA

Thuật toán

1. Duyệt mask từ 1 đến 2ⁿ-1 (tổ hợp)
2. Với mỗi mask, tạo chuỗi con
3. Sinh tất cả hoán vị của chuỗi con (next_permutation)

Chương trình

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

void printAllStrings(string str) {
    int n = str.size();
    int total = pow(2, n);
    
    for (int mask = 1; mask < total; mask++) {
        string sub = "";
        for (int j = 0; j < n; j++)
            if (mask & (1 << j)) sub += str[j];
        
        sort(sub.begin(), sub.end());
        do {
            cout << sub << endl;
        } while (next_permutation(sub.begin(), sub.end()));
    }
}

int main() {
    printAllStrings("ABCD");
    return 0;
}