Dùng phương pháp đệ quy. Nhận thấy với mổi dấu hỏi sẽ có nhiều nhất 4 trường hợp điền dấu ngoặc. Do đó có thể đệ quy để bỏ tìm các trường hợp có thể tạo ra dãy ngoặc hợp lệ.
Độ phức tạp
Subtask :
Gọi là số cách có thể tạo ra dãy ngoặc hợp lệ từ kí tự thứ đến . Ta có công thức
với mọi kí tự sao cho kí tự ngoặc ở vị trí là ngoặc đóng của ngoặc ở vị trí
Ta có thể dùng quy hoạch động kết hợp đệ quy có nhớ để giải bài toán với độ phức tạp
