Cách tìm tất cả tổ hợp ngoặc mở/đóng từ số k cho trước bằng C#

Tạo hàm backtrack cập nhật chuỗi hiện tại nếu số ngoặc mở nhỏ hơn n hoặc ngoặc đóng nhỏ hơn ngoặc mở. Khi độ dài chuỗi hiện tại bằng 2*n, thêm vào mảng kết quả. Có thể theo dõi đơn giản bằng cách đếm số cặp { } đã đặt. Có thể thêm ngoặc mở nếu vẫn còn để đặt. Và có thể thêm ngoặc đóng nếu nó không vượt quá số ngoặc mở.

Ví dụ

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace ConsoleApplication
{
    public class BackTracking
    {
        public void Brackets()
        {
            char[] arr = new char[4];
            FindSequence(arr, 0, 2, 0, 0);
        }

        private static void FindSequence(char[] arr, int index, int N, int openBracket, int closeBracket)
        {
            if (closeBracket == N)
            {
                StringBuilder s = new StringBuilder();
                for (int i = 0; i < arr.Length; i++)
                {
                    s.Append(arr[i]);
                }
                Console.WriteLine(s);
                s = null;
                return;
            }
            else
            {
                if (openBracket > closeBracket)
                {
                    arr[index] = '}';
                    FindSequence(arr, index + 1, N, openBracket, closeBracket + 1);
                }
                if (openBracket < N)
                {
                    arr[index] = '{';
                    FindSequence(arr, index + 1, N, openBracket + 1, closeBracket);
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BackTracking b = new BackTracking();
            b.Brackets();
        }
    }
}

Kết quả

{}{} {{}}

Giải thích: Với n=2, có 2 tổ hợp ngoặc hợp lệ: {}{} và {{}}. Thuật toán backtracking sinh ra tất cả chuỗi ngoặc cân bằng đúng cú pháp.