In tất cả các tổ hợp dấu ngoặc cân bằng trong C ++

Trong bài toán này, chúng ta được cung cấp một số nguyên n. Nhiệm vụ của chúng tôi là in tất cả các cặp có n dấu ngoặc đơn cân đối.

Dấu ngoặc đơn cân đối là các cặp dấu ngoặc có ký hiệu đóng cho mọi ký hiệu mở tương ứng. Ngoài ra, các cặp phải được lồng vào nhau một cách hợp lý.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Để giải quyết vấn đề này, chúng ta cần theo dõi các cặp dấu ngoặc. Số lượng ban đầu của dấu ngoặc là 0. Sau đó, chúng ta sẽ đệ quy một hàm cho đến khi tổng số dấu ngoặc nhỏ hơn n. Đếm dấu ngoặc, gọi đệ quy cho dấu ngoặc dựa trên số lượng. Nếu số lượng dấu ngoặc mở nhiều hơn số đóng, hãy đặt dấu ngoặc đóng và sau đó tính số cặp còn lại, nếu dấu ngoặc mở nhỏ hơn n thì gọi đệ quy cho các cặp dấu ngoặc còn lại.

Ví dụ

Đoạn mã dưới đây hiển thị việc triển khai giải pháp của chúng tôi,

# 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;
}

Đầu ra

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