查找格式正确的括号的所有组合

问题描述

这是在和朋友聊天时想到的，我想我会在这里问，因为这是一个有趣的问题，并且希望看到其他人的解决方案.

This came up while talking to a friend and I thought I'd ask here since it's an interesting problem and would like to see other people's solutions.

任务是编写一个函数 Brackets(int n) 来打印 1...n 中 格式良好 括号的所有组合.对于 Brackets(3) 输出将是

The task is to write a function Brackets(int n) that prints all combinations of well-formed brackets from 1...n. For Brackets(3) the output would be

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

推荐答案

尝试了一下.. C# 也是.

Took a crack at it.. C# also.

public void Brackets(int n) {
    for (int i = 1; i <= n; i++) {
        Brackets("", 0, 0, i);
    }
}

private void Brackets(string output, int open, int close, int pairs) {
    if((open==pairs)&&(close==pairs)) {
        Console.WriteLine(output);
    } else {
        if(open<pairs)
            Brackets(output + "(", open+1, close, pairs);
        if(close<open)
            Brackets(output + ")", open, close+1, pairs);
    }
}

递归利用这样一个事实，即您添加的左括号永远不能超过所需的对数，并且您添加的右括号永远不能多于左括号.

The recursion is taking advantage of the fact that you can never add more opening brackets than the desired number of pairs, and you can never add more closing brackets than opening brackets..

这篇关于查找格式正确的括号的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！