`

LeetCode 22 - Generate Parentheses

 
阅读更多

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

public List<String> generateParenthesis(int n) {
    char[] pars = new char[n*2];
    List<String> result = new ArrayList<>();
    generate(result, n, n, pars, 0);
    return result;
}

private void generate(List<String> result, int l, int r, char[] pars, int index) {
    if(l>r) return;
    if(r==0) {
        result.add(new String(pars));
        return;
    }
    if(l>0) {
        pars[index] = '(';
        generate(result, l-1, r, pars, index+1);
    }
    if(r>l) {
        pars[index] = ')';
        generate(result, l, r-1, pars, index+1);
    }
}

 

C++的做法略有不同,C的char数组元素个数必需为2n+1个,因为最后一个元素用来存储终止符 ' \0 '。

vector<string> generateParenthesis(int n) {
    vector<string> result;
    char p[n*2+1];
    p[n*2] = '\0';
    generate(result, p, n, n, 0);
    return result;
}

void generate(vector<string>& result, char* p, int l, int r, int i) {
    if(l > r) return;
    if(r == 0) {
        result.push_back(string(p));
        return;
    }
    if(l > 0) {
        p[i] = '(';
        generate(result, p, l-1, r, i+1);
    }
    if(l < r) {
        p[i] = ')';
        generate(result, p, l, r-1, i+1);
    }
}

 

分享到:
评论

相关推荐

    java-leetcode题解之22-Generate-Parentheses

    java入门 java_leetcode题解之22_Generate_Parentheses

    leetcode答案-LeetCode:不要放弃

    leetcode 答案LeetCode 算法的复杂度分析。...因为是递回求解,所以很抽象不好懂,这里以leetcode的generate-parentheses一道题目为例,给定n,要找出n个括号的各种组合,例如n=2 ,答案会是[(()), ()()]

    leetcode2-Algorithms-Practice:创建此repo是为了跟踪我在解决问题方面的进展

    leetcode 2 LeetCode-练习 我的 ...Generate Parentheses 运行时间:164 毫秒内存使用:22.5 MB 26. Remove Duplicates from Sorted Array 运行时间:100 毫秒内存使用:15.2 MB 27. Remove Element

    leetcode信封-LeetCode:LeetCode解题

    leetcode信封 ...GeneratorParenthesis.java //22. Generate Parentheses | ImplementstrStr.java //28. Implement strStr() │ LongestIncreasingSubsequence.java 300.Longest Increasing Subsequence | ...

    leetcode中国-LeetCodeAnswerCollections:LeetCode题解精选代码收集

    generate-parentheses【】【中等】 这是一道递归题目,想法很重要,保证括号合法性是另一个要点 private List result; public List generateParenthesis(int n) { result = new ArrayList(); _generate(0, 0, n, "")...

    _leetcode-python.pdf

    - Generate Parentheses: 生成所有可能的有效的括号组合。 - Merge k Sorted Lists: 合并k个排序链表。 - Swap Nodes in Pairs / Reverse Nodes in k-Group: 这两个问题涉及到在链表中按特定规则交换节点或反转节点...

    leetcode530-algorithm:算法

    leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 ...Parentheses ...Generate Parentheses 028 Implement strStr() 031 Next Permutat

    程序员面试宝典LeetCode刷题手册

    第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without ...22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli

    lrucacheleetcode-leetcode:leetcode

    lru缓存leetcode leetcode 1. Two Sum 2. Add Two ...Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3

    LeetCode 刷题汇总1

    * 生成括号(Generate Parentheses):生成所有可能的括号组合。 6. 字符串匹配: * 正则表达式匹配(Regular Expression Matching):实现正则表达式匹配。 * 实现strStr()(Implement strStr()):实现字符串...

    c++-c++编程基础之leetcode题解第22题括号生成.zip

    第22题,"括号生成"(Generate Parentheses),是其中一道经典的动态规划问题,旨在考察程序员对递归、回溯以及组合的理解。这道题目要求我们生成所有有效的括号组合,即所有符合括号开闭规则的字符串。 题目描述:...

    LeetCode 括号生成

    题目来源:https://leetcode-cn.com/problems/generate-parentheses/submissions/ 题目 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。 例如,给出 n = 3,生成结果为...

    leetcode添加元素使和等于-programmer_practices:算法实践

    Generate Parentheses 18 3 sum 扩展版, 外层多套一个循环即可。注意判断重复及细节优化 19 细节:nodelist前插入一个dummy node. 删除倒数第n 等于正数查到len - n 20 用stack 最后stack应该是空的 21 遍历直到二...

    Dir-For-LeetCode

    022_Generate_Parentheses 023_Merge_k_Sorted_Lists 024_Swap_Nodes_in_Pairs 025_Reverse_Nodes_in_k-Group 026_Remove_Duplicates_from_Sorted_Array 027_Remove_Element 028_Implement_strStr() 029_...

    LeetCode

    题目0022:"生成括号"(Generate Parentheses) 这是一个关于回溯算法和组合问题的题目。目标是生成所有有效的括号组合,这些括号字符串必须符合正确的左右括号匹配规则。通过递归或者动态规划的策略,我们可以构建...

    Coding Interview In Java

    237 Generate Parentheses 575 238 Combination Sum 577 239 Combination Sum II 579 240 Combination Sum III 581 241 Combinations 583 242 Letter Combinations of a Phone Number 587 243 Restore IP Addresses ...

    Amazon近半年电面题.pdf

    18. GenerateParentheses: 生成所有可能的有效的括号组合,这涉及到回溯算法。 19. MergekSortedLists: 合并k个已排序链表,这需要用到优先队列或者归并排序的思想。 20. SwapNodesinPairs: 在链表中交换每两个...

Global site tag (gtag.js) - Google Analytics