LeetCode Summary
  • Introduction
  • DP, 动态规划类
    • Best Time to Buy and Sell Stock III 题解
    • Best Time to Buy and Sell Stock 题解
    • Climbing Stairs 题解
    • Decode Ways 题解
    • Distinct Subsequences 题解
    • Edit Distance 题解
    • Interleaving String 题解
    • Longest Palindromic Substring 题解
    • Maximum Product Subarray 题解
    • Maximum Subarray 题解
    • Minimum Path Sum 题解
    • Palindrome Partitioning 题解
    • Palindrome Partitioning II 题解
    • Scramble String 题解
    • Triangle 题解
    • Unique Binary Search Trees 题解
    • Unique Paths II 题解
    • Word Break 题解
    • Word Break II 题解
  • list, 链表相关
    • Add Two Numbers 题解
    • Convert Sorted List to Binary Search Tree 题解
    • Copy List with Random Pointer 题解
    • Insertion Sort List 题解
    • LRU Cache 题解
    • Linked List Cycle 题解
    • Linked List Cycle II 题解
    • Merge Two Sorted Lists 题解
    • Merge k Sorted Lists 题解
    • Partition List 题解
    • Remove Duplicates from Sorted List 题解
    • Remove Duplicates from Sorted List II 题解
    • Remove Nth Node From End of List 题解
    • Reorder List 题解
    • Reverse Linked List II 题解
    • Reverse Nodes in k-Group 题解
    • Rotate List 题解
    • Sort List 题解
    • Swap Nodes in Pairs 题解
  • binary tree, 二叉树相关
    • Balanced Binary Tree 题解
    • Binary Tree Inorder Traversal 题解
    • Binary Tree Level Order Traversal 题解
    • Binary Tree Level Order Traversal II 题解
    • Binary Tree Maximum Path Sum 题解
    • Binary Tree Postorder Traversal 题解
    • Binary Tree Preorder Traversal 题解
    • Binary Tree Zigzag Level Order Traversal 题解
    • Construct Binary Tree from Inorder and Postorder Traversal 题解
    • Construct Binary Tree from Preorder and Inorder Traversal 题解
    • Convert Sorted List to Binary Search Tree 题解
    • Flatten Binary Tree to Linked List 题解
    • Maximum Depth of Binary Tree 题解
    • Minimum Depth of Binary Tree 题解
    • Path Sum 题解
    • Path Sum II 题解
    • Populating Next Right Pointers in Each Node 题解
    • Populating Next Right Pointers in Each Node II 题解
    • Recover Binary Search Tree 题解
    • Same Tree 题解
    • Sum Root to Leaf Numbers 题解
    • Symmetric Tree 题解
    • Unique Binary Search Trees 题解
    • Unique Binary Search Trees II 题解
    • Validate Binary Search Tree 题解
  • sort, 排序相关
    • 3Sum Closest 题解
    • 3Sum 题解
    • 4Sum 题解
    • Insert Interval 题解
    • Longest Consecutive Sequence 题解
    • Merge Intervals 题解
    • Merge Sorted Array 题解
    • Remove Duplicates from Sorted Array 题解
    • Remove Duplicates from Sorted Array II 题解
    • Sort Colors 题解
    • Two Sum 题解
  • search, 搜索相关
    • First Missing Positive 题解
    • Find Minimum in Rotated Sorted Array 题解
    • Find Minimum in Rotated Sorted Array II 题解
    • Median of Two Sorted Arrays 题解
    • Search Insert Position 题解
    • Search a 2D Matrix 题解
    • Search for a Range 题解
    • Search in Rotated Sorted Array 题解
    • Search in Rotated Sorted Array II 题解
    • Single Number 题解
    • Single Number II 题解
  • math, 数学类相关
    • Add Binary 题解
    • Add Two Numbers 题解
    • Divide Two Integers 题解
    • Gray Code 题解
    • Integer to Roman 题解
    • Multiply Strings 题解
    • Palindrome Number 题解
    • Plus One 题解
    • [Pow(x, n) 题解](math/Pow(x,-n).md)
    • Reverse Integer 题解
    • Roman to Integer 题解
    • [Sqrt(x) 题解](math/Sqrt(x).md)
    • [String to Integer (atoi) 题解](math/String-to-Integer-(atoi).md)
    • Valid Number 题解
  • string, 字符串处理相关
    • Anagrams 题解
    • Count and Say 题解
    • Evaluate Reverse Polish Notation 题解
    • [Implement strStr() 题解](string/Implement-strStr().md)
    • Length of Last Word 题解
    • Longest Common Prefix 题解
    • Longest Palindromic Substring 题解
    • Longest Substring Without Repeating Characters 题解
    • Longest Valid Parentheses 题解
    • Minimum Window Substring 题解
    • Regular Expression Matching 题解
    • Reverse Words in a String 题解
    • Simplify Path 题解
    • Text Justification 题解
    • Valid Parentheses 题解
    • Wildcard Matching 题解
    • ZigZag Conversion 题解
  • combination and permutation, 排列组合相关
    • Combinations 题解
    • Combination Sum 题解
    • Combination Sum II 题解
    • Letter Combinations of a Phone Number 题解
    • Next Permutation 题解
    • Palindrome Partitioning 题解
    • Permutation Sequence 题解
    • Permutations 题解
    • Permutations II 题解
    • Subsets 题解
    • Subsets II 题解
    • Unique Paths 题解
  • matrix, 二维数组, 矩阵相关
    • Rotate Image 题解
    • Set Matrix Zeroes 题解
    • Spiral Matrix 题解
    • Spiral Matrix II 题解
    • Maximal Rectangle 题解
  • 回溯, BFS/DFS
    • Clone Graph 题解
    • Generate Parentheses 题解
    • N-Queens 题解
    • N-Queens II 题解
    • Restore IP Addresses 题解
    • Sudoku Solver 题解
    • Surrounded Regions 题解
    • Word Ladder 题解
    • Word Ladder II 题解
    • Word Search 题解
  • greedy, 贪心
    • Best Time to Buy and Sell Stock II 题解
    • Jump Game 题解
    • Jump Game II 题解
  • 其他
    • Candy 题解
    • Container With Most Water 题解
    • Gas Station 题解
    • Gray Code 题解
    • Max Points on a Line 题解
    • [Pascal's Triangle 题解](others/Pascal's-Triangle.md)
    • [Pascal's Triangle II 题解](others/Pascal's-Triangle-II.md)
    • Remove Element 题解
    • Trapping Rain Water 题解
Powered by GitBook
On this page

Was this helpful?

  1. 回溯, BFS/DFS

Generate Parentheses 题解

PreviousClone Graph 题解NextN-Queens 题解

Last updated 5 years ago

Was this helpful?

题目来源：

> 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: "((()))", "(()())", "(())()", "()(())", "()()()"

解题思路：

用递归，一个括号一个括号放，只要有左括号在，随时都可以放；放右括号时，已经放好的左括号数量要多余已放好的右括号才可以。

void gen(vector<string> &result, string pre, int left, int right)
{
   if(left < 0 || right < 0) return;
   if(left == 0 && right == 0)
   {
       result.push_back(pre);
       return;
   }    
   if(left > 0)
       gen(result, pre+"(", left-1, right);
   if(left < right) //  (()
       gen(result, pre+")", left, right-1);
}

vector<string> generateParenthesis(int n) 
{
   vector<string> result;
   string pre;
   gen(result, pre, n, n);
   return move(result);
}
Generate Parentheses