By yusijia

Updated:

Contents
  1. 1. 题目：
  2. 2. 分析
    1. 2.1. 贪心策略：
1
2
3
4
5
6
7
8
/*
 * Given n pairs of parentheses, write a function to generate all combinations 
 * of well-formed parentheses.

 * For example, given n = 3, a solution set is:

 * "((()))", "(()())", "(())()", "()(())", "()()()" 
 */

题目：

给n对括号，求重新排列组合后产生的所有合法组合的可能

1
2
3
4
5
6
例如： 
"((()))"
"(()())"
"(())()"
"()(())"
"()()()"

分析

首先容易想到用dfs

贪心策略：

  • 优先用’(‘
  • 回溯的时候，当’(‘括号的剩余量小于’)’可以考虑用’)’
  • 当’(‘和’)’数量相等时优先用’(‘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//left: 左括号的剩余量
//right：右括号的剩余量
//s： 临时存储当前结果
void solve(int left, int right, string s, vector<string> &result){
    if(left == 0 && right == 0){
        result.push_back(s);
        //cout << s << endl;
    }
    if(left > 0 ){
        solve(left - 1, right, s + '(', result);
    }
    if(right > 0 && right > left){
        solve(left, right - 1, s + ')', result);
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;  
    if (n == 0)  
        return result;  
    solve(n, n, "", result);  
    return result;  
}
Contents
  1. 1. 题目：
  2. 2. 分析
    1. 2.1. 贪心策略：