括号生成 | Nameless Site

来源Leetcode第22题括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

回溯

其实可以把这道题看作是一道完全二叉树的题目，根结点为’(‘,树的最长路径为2n,那么只需当当前路径长度小于输入的n值时即可增加’(‘和’)’。
采用两个变量open、close分别标记’(‘和’)’的数量，那么满足以下两个条件即可进入更深一层递归：

当open < n 时，说明当前增加的’(‘还没到达上限，仍可继续增加
当close < opne时，说明此时的’)’数量小于’(‘数量，可以增加’)’的数量以达到配对’(‘

代码如下：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }

        if (open < max)
            backtrack(ans, cur+"(", open+1, close, max);
        if (close < open)
            backtrack(ans, cur+")", open, close+1, max);
    }
}

规划条件

来自于题解里的另一种解法：

当我们清楚所有 i<n 时括号的可能生成排列后，对与 i=n 的情况，我们考虑整个括号排列中最左边的括号。
它一定是一个左括号，那么它可以和它对应的右括号组成一组完整的括号 “( )”，我们认为这一组是相比 n-1 增加进来的括号。

那么，剩下 n-1 组括号有可能在哪呢？

[这里是重点，请着重理解]

剩下的括号要么在这一组新增的括号内部，要么在这一组新增括号的外部（右侧）。

既然知道了 i<n 的情况，那我们就可以对所有情况进行遍历：

“(“ + [i=p时所有括号的排列组合] + “)” + [i=q时所有括号的排列组合]

其中 p + q = n-1，且 p q 均为非负整数。

事实上，当上述 p 从 0 取到 n-1，q 从 n-1 取到 0 后，所有情况就遍历完了。

注：上述遍历是没有重复情况出现的，即当 (p1,q1)≠(p2,q2) 时，按上述方式取的括号组合一定不同。

简单来说，在求N个括号的排列组合时，把第N种情况（也就是N个括号排列组合）视为单独拿一个括号E出来，剩下的N-1个括号分为两部分，P个括号和Q个括号，P+Q=N-1，然后这两部分分别处于括号E内和括号E的右边，各自进行括号的排列组合。由于我们是一步步计算得到N个括号的情况的，所以小于等于N-1个括号的排列组合方式我们是已知的（用合适的数据结构存储，方便后续调用，且在存储时可利用特定数据结构实现题目某些要求，如排序，去重等），且P+Q=N-1，P和Q是小于等于N-1的，所以我们能直接得到P个和Q个括号的情况，进而得到N个括号的结果！

这个解法的算法思想很巧妙，这个算法主要的基点就是将排列组合的情况分为了括号内和括号外这两种情况，且仅存在两种情况！至于为什么，原因在于楼主的算法的前提是单独拿出来的括号E的左边在N个括号所有排列组合情况中都是处于最左边，所以不存在括号位于括号E的左边的情况。因此，N-1个括号（拿出了括号E）仅可能分布于括号E内和括号E外，分为两种子情况讨论！(其实可以证明形如 “()A” 是会有和 “A()” 重复部分的) 这种思想还可以应用于其他类似的题的求解中，即怎样合理高效的利用前面步骤的计算结果得出当前步骤结果，从而得出最终结果。

代码如下：

public List<String> generateParenthesis(int n) {
		LinkedList<LinkedList<String>> result = new LinkedList<LinkedList<String>>();
		if (n == 0)
			return result.get(0);
		LinkedList<String> list0 = new LinkedList<String>();
		list0.add("");
		result.add(list0);
		LinkedList<String> list1 = new LinkedList<String>();
		list1.add("()");
		result.add(list1);
		for (int i = 2; i <= n; i++) {
			LinkedList<String> temp = new LinkedList<String>();
			for (int j = 0; j < i; j++) {
				List<String> str1 = result.get(j);
				List<String> str2 = result.get(i - 1 - j);
				for (String s1 : str1) {
					for (String s2 : str2) {
						String el = "(" + s1 + ")" + s2;
						temp.add(el);
					}
				}

			}
			result.add(temp);
		}
		return result.get(n);
	}

题解摸了

来自题解的另一种解法，看不懂，困了，摸了

class Solution
{
public:
    inline int tatal(int num[], int t)
    {
        int result = 0;
        for(int i = 0; i < t; i++)
            result += num[i];
        return result;
    }
    inline bool equal(int num[], int t)
    {
        for(int i = 0; i < t; i++)
        {
            if(num[i] != 1)
                return false;
        }
        return true;
    }
    inline string once(int num[], int t)
    {
        string temp;
        for(int i = 0; i < t; i++)
        {
            temp += '(';
            for(int j = 0; j < num[i]; j++)
            {
                temp += ')';
            }
        }
        return temp;
    }
    vector<string> generateParenthesis(int n)
    {
        vector<string> result;
        if(n <= 0)
        {
            string temp0 = "";
            result.push_back(temp0);
            return result;
        }
        int *num = new int[n];
        for(int i = 0; i < n; i++)
            num[i] = 0;
        num[n-1] = n;
        if(n >= 1)
        {
            string temp0 = once(num, n);
            result.push_back(temp0);
        }
        if(n < 2)
        {
            delete [] num;
            return result;
        }

        while(true)
        {
            if(num[n-1] > 1)
            {
                num[n-1]--;
                num[n-2]++;
                string temp0 = once(num, n);
                result.push_back(temp0);
                if(equal(num, n))
                    break;
                else
                    continue;
            }
            for(int i = n - 2; i >= 0; i--)
            {
                num[i] += 1;
                if((num[i] > i + 1)||(tatal(num,i+1) > i + 1))
                {
                    num[i] = 0;
                }
                else
                {
                    break;
                }
            }
            num[n-1] = n - tatal(num,n-2);
            string temp1 = once(num, n);
            result.push_back(temp1);
            if(equal(num, n))
                break;
        }

        delete [] num;
        return result;
    }
};

闭合数

来自于官方解答的闭合数，其实和动态规划是差不多的，也摸了，明天再看了。

方法三：闭合数
思路

为了枚举某些内容，我们通常希望将其表示为更容易计算的不相交子集的总和。

考虑有效括号序列 S 的闭包数：至少存在 index >= 0，使得 S[0], S[1], …, S[2*index+1]是有效的。显然，每个括号序列都有一个唯一的闭包号。我们可以尝试单独列举它们。

算法

对于每个闭合数 c，我们知道起始和结束括号必定位于索引 0 和 2c + 1。然后两者间的 2c 个元素一定是有效序列，其余元素一定是有效序列。

代码如下：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c)
                for (String left: generateParenthesis(c))
                    for (String right: generateParenthesis(n-1-c))
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }
}