พิมพ์สตริงความยาว k ทั้งหมดจากชุดตัวอักษร n ตัวใน C++

ปัญหา

ได้รับชุดตัวอักษร และจำนวนเต็มบวก k พิมพ์สตริงความยาว k ทั้งหมดที่สร้างได้จากชุดตัวอักษร เช่น set={'x','y','z'}, k=2 → xy, xz, yz (หมายเหตุ: ตัวอย่าง Output ในต้นฉบับดูเหมือนจะเป็น Permutation ไม่ใช่ Combination)

วิธีแก้

จำนวนสตริงทั้งหมด = n^k ใช้ Recursive สร้างสตริงจากสตริงว่าง เพิ่มตัวอักษรทีละตัว

ตัวอย่างโค้ด

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

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

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

ผลลัพธ์

aaa aab aba abb baa bab bba bbb

คำอธิบาย

โค้ดสร้าง String ทุกความเป็นไปได้ (With Repetition) ความยาว k จาก n ตัวอักษร = n^k = 2^3 = 8 สตริง

หมายเหตุ: ตัวอย่างในโจทย์ (xy, xz, yz) ดูเหมือนจะเป็น Combination without repetition (nCk) แต่โค้ดทำ With repetition (n^k) หากต้องการ Combination ต้องเพิ่มเงื่อนไข index parameter