美文网首页
给出一个偶数,获取所有的括号组合

给出一个偶数,获取所有的括号组合

作者: zxqian1991 | 来源:发表于2017-06-15 13:28 被阅读37次

    现在给出一个偶数n,要求打印出所有的括号的组合,括号有两种,分别是()
    要求: 左括号右边一定得有一右括号和它对应,右括号的左边也一定有一个左括号对应,举个例子,当n=2的时候,只有()这种情况,)(这种情况是不可行的。

    这个问题听起来其实有点类似于给你一个数,比如10,然后打印出所有的二进制的可能性。

    分析

    那么,拿到手后,首先是进行简单的分析,有左括号,一定有一个右括号对应,而且必须是一对对的,那么可以有以下结论:

    1. 任意一个位置的左侧的左括号的数量 大于等于 右括号的数量(第一个位置那么就肯定是左括号了)
    2. 任意一个位置的左侧,左括号的数量 小于等于 n/2

    那么就可以通过这两点来进行递归的判断,代码如下:

    function getSynbols(number, sumOnly, left, right, str, arr) {
        arr = arr == undefined ? (sumOnly ? [0] : []) : arr;
        left = left || 0;
        right = right || 0;
        str = str || '';
        let half = number / 2;
        if (right + left == number) {
            if (sumOnly) {
                arr[0]++;
            } else {
                arr.push(str);
            }
        } else {
            if (number % 2 == 0) {
                if (left < half) {
                    getSynbols(number, sumOnly, left + 1, right, str + "(", arr);
                    if (left > 0 && right < left) getSynbols(number, sumOnly, left, right + 1, str + ")", arr);
                } else {
                    getSynbols(number, sumOnly, left, right + 1, str + ")", arr);
                }
            } else {
                console.log("请输入一个偶数");
            }
        }
        return arr;
    };
    

    这里的参数说明如下:

    1. number 表示输入的数,这个数字必须是偶数。
    2. sumOnly 表示是否只统计数量,而不将结果存储到数组中(防止数量太大,撑爆内存)
    3. left 表示左括号的数量
    4. right 表示右括号的数量
    5. str 表示当前的已经拼接的字符串
    6. arr 存放结果的数组

    相关文章

      网友评论

          本文标题:给出一个偶数,获取所有的括号组合

          本文链接:https://www.haomeiwen.com/subject/gdnyqxtx.html