题解 | #括号生成#

这是一道典型的回溯算法问题，可以将此问题转化为：现在共有2n个位置，每个位置放字符(或者)，组成所有的括号组合。

根据回溯框架我们迅速写出一套伪代码：

void backtrack(int n, int i, string&track, vector<string>&res){
	if(i==2*n){
    	res.push_back(track);
     	return;
    }
  	
  for x in ['(', ')']:
  	track.push(x);
  	backtrack(n, i++, track, res);
  	track.pop();
}

然后，根据括号的合法情况，进行剪枝操作。去掉当前右括号比左括号多的情况。因此，分别使用left，right分别技术剩余的左右括号数量。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    void backtrack(int left, int right, string& tmp, vector<string>& res){
        if(left<0 || right<0) return;
        if(left>right) return; //左括号剩下的多，说明tmp中右括号多,不合法
        if(left == 0 && right==0){
            res.push_back(tmp);
            return;
        }
        
        tmp.push_back('(');
        backtrack(left-1, right, tmp, res);
        tmp.pop_back();
        
        tmp.push_back(')');
        backtrack(left, right-1, tmp, res);
        tmp.pop_back();
        
    }
    
    vector<string> generateParenthesis(int n) {
        // write code here
        string tmp;
        vector<string> res;
        backtrack(n,n, tmp, res);
        return res;
    }
};

时间复杂度为 递归次数*递归函数本身。

递归次数主要看"状态"的个数，backtrack函数可以看出，left,right, track这三个变量的所有组合个数就是该函数状态的个数。 left和right的组合很容易了解，一共有n的平放种，track的取值范围虽然是0-2n,但是每个胀肚有指数级的括号组合，不好计算。

因此，backtrack函数对应算法的时间复杂度为指数（卡特兰数），空间复杂度为o(1)。