In tất cả chuỗi độ dài k từ tập n ký tự C++

Cho tập ký tự kích thước n và số k. In tất cả chuỗi độ dài k có thể tạo (cho phép lặp ký tự).

Ví dụ

set = {'a', 'b'}, k = 3 → aaa, aab, aba, abb, baa, bab, bba, bbb (2^3 = 8 chuỗi)

Thuật toán đệ quy

Xây dựng chuỗi từ rỗng, mỗi bước thêm 1 ký tự từ tập. Khi độ dài = k, in ra.

Chương trình mẫu

#include <bits/stdc++.h>
using namespace std;

void printKLengthString(char set[], string prefix, int n, int k) {
    if (k == 0) {
        cout << prefix << "\t";
        return;
    }
    for (int i = 0; i < n; i++) {
        printKLengthString(set, prefix + set[i], n, k - 1);
    }
}

int main() {
    char set[] = {'a', 'b'};
    int n = 2, k = 3;
    printKLengthString(set, "", n, k);
    return 0;
}

Kết quả

aaa aab aba abb baa bab bba bbb

Độ phức tạp: O(n^k × k) thời gian (n^k chuỗi, mỗi chuỗi copy O(k)), O(k) stack space.

Lưu ý: Đây là variation with repetition (chỉnh lặp). Nếu không cho lặp, dùng hoán vị/backtracking với mảng visited.

Ứng dụng: Sinh password, test case, brute force, tổ hợp sinh.