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

ในปัญหานี้ เราได้รับจำนวนเต็ม n งานของเราคือพิมพ์วงเล็บสมดุล n คู่ที่เป็นไปได้ทั้งหมด

วงเล็บสมดุล เป็นคู่วงเล็บที่มีสัญลักษณ์ปิดสำหรับทุกสัญลักษณ์เปิดที่เกี่ยวข้อง นอกจากนี้ คู่ควรซ้อนกันอย่างเหมาะสม

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

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

เพื่อแก้ปัญหานี้ เราจำเป็นต้องติดตามคู่ของวงเล็บ จำนวนวงเล็บเริ่มต้นคือ 0 จากนั้นเราจะเรียกใช้ฟังก์ชันซ้ำจนกว่าจำนวนวงเล็บทั้งหมดจะน้อยกว่า n นับวงเล็บ เรียกวงเล็บซ้ำตามการนับ หากจำนวนวงเล็บเปิดมากกว่าการปิด ให้ใส่วงเล็บปิดแล้วนับจำนวนคู่ที่เหลือ ถ้าวงเล็บเปิดน้อยกว่า n ให้เรียกคู่วงเล็บที่เหลือซ้ำๆ

ตัวอย่าง

โค้ดด้านล่างพร้อมการแสดงการใช้งานโซลูชันของเรา

# 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);
   getchar();
   return 0;
}

ผลลัพธ์

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