พิมพ์ชุดวงเล็บสมดุลทั้งหมดใน C++

ภาพรวมปัญหา

ได้รับจำนวนเต็ม n ต้องพิมพ์ชุดวงเล็บปีกกา { } ที่สมดุล (balanced) ทั้งหมด จำนวน n คู่

วงเล็บสมดุล (Balanced Parentheses)

คู่วงเล็บที่มีวงเล็บปิดสำหรับทุกวงเล็บเปิด และซ้อนกันได้ถูกต้อง

ตัวอย่าง

Input: n = 2
Output: {}{} {{}}

วิธีแก้ปัญหา (Recursion + Backtracking)

1. ติดตามจำนวนวงเล็บเปิด (open) และวงเล็บปิด (close)
2. ถ้า close == n → พิมพ์ผลลัพธ์
3. ถ้า open > close → เพิ่ม } แล้วเรียกซ้ำ
4. ถ้า open < n → เพิ่ม { แล้วเรียกซ้ำ

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

#include <iostream>
using namespace std;

#define MAX_COUNT 100

void printParenthesesPairs(int pos, int n, int open, int close) {
    static char str[MAX_COUNT];
    if (close == n) {
        cout << str << endl;
        return;
    } else {
        if (open > close) {
            str[pos] = '}';
            printParenthesesPairs(pos + 1, n, open, close + 1);
        }
        if (open < n) {
            str[pos] = '{';
            printParenthesesPairs(pos + 1, n, open + 1, close);
        }
    }
}

int main() {
    int n = 3;
    cout << "All parentheses pairs of length " << n << " are:\n";
    if (n > 0)
        printParenthesesPairs(0, n, 0, 0);
    return 0;
}

ผลลัพธ์ (Output)

All parentheses pairs of length 3 are:
{}{}{} {}{{}} {{}}{} {{}{}} {{{}}}