Chương trình C ++ để tìm n chuỗi dấu ngoặc hợp lệ

Giả sử chúng ta có một số n. Như chúng ta đã biết, một chuỗi ngoặc là một chuỗi chỉ chứa các ký tự "(" và ")". Dãy ngoặc hợp lệ là một dãy ngoặc có thể được chuyển đổi thành một biểu thức số học đúng bằng cách chèn các ký tự "1" và "+" vào giữa các ký tự ban đầu của dãy. Vì vậy, nếu một chuỗi ngoặc giống như "() ()" thì điều này là hợp lệ vì chúng ta có thể đặt 1 giống như "(1) + (1)". Từ số n, chúng ta phải tìm chính xác n dãy dấu ngoặc hợp lệ khác nhau có thể có độ dài 2n.

Vì vậy, nếu đầu vào là n =4, thì đầu ra sẽ là ["() () () ()", "(()) () ()", "((())) ()", "(((())))"]

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

for initialize k := 1, when k <= n, update (increase k by 1), do:
   for initialize i := 1, when i <= k, update (increase i by 1), do:
      print "("
   for initialize i := 1, when i <= k, update (increase i by 1), do:
      print ")"
   for initialize i := k + 1, when i <= n, update (increase i by 1), do:
      print "()"
   go to next line

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

void solve(int n) {
   for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= k; i++)
         cout << "(";
      for (int i = 1; i <= k; i++)
         cout << ")";
      for (int i = k + 1; i <= n; i++)
         cout << "()";
      cout << endl;
   }
}
int main() {
   int n = 4;
   solve(n);
}

Đầu vào

4

Đầu ra

()()()()
(())()()
((()))()
(((())))