Parentheses generates

The number n represents the logarithm that generates parentheses. Design a function that generates all possible and valid parentheses.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/ge… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: exhaustive method

Get all possible combinations recursively, then determine if each combination is a valid parenthesis combination, if so, add it to the result set, and finally return the matching result set.

Solution two: backtracking

The method is also recursive, but the next character can be determined by the number of left and right parentheses that have appeared. In this way, the final recursive result is a valid combination of parentheses, which is efficient.

import java.util.ArrayList;
import java.util.List;

public class LeetCode_022 {
    /** * Brute force method **@param n
     * @return* /
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateAllPossibleResults(new char[2 * n], 0, result);
        return result;
    }

    /** * recursion: an array of 2*n characters, each of which has 2 possibilities, until the array is filled to check for **@param current
     * @param pos
     * @param result
     */
    public static void generateAllPossibleResults(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            // When the array is full, verify that it matches
            if (valid(current)) {
                result.add(newString(current)); }}else {
            / / recursion
            current[pos] = '(';
            generateAllPossibleResults(current, pos + 1, result);
            current[pos] = ') ';
            generateAllPossibleResults(current, pos + 1, result); }}/** * Determine whether the conditions are met **@param current
     * @return* /
    public static boolean valid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false; }}return balance == 0;
    }

    static List<String> res = new ArrayList<>();

    /** * method 2: backtrace method **@param n
     * @return* /
    public static List<String> generateParenthesis2(int n) {
        if (n <= 0) {
            return res;
        }
        getParenthesis("", n, n);
        return res;
    }

    private static void getParenthesis(String str, int left, int right) {
        if (left == 0 && right == 0) {
            res.add(str);
            return;
        }
        if (left == right) {
            // The number of left and right parentheses is equal
            getParenthesis(str + "(", left - 1, right);
        } else if (left < right) {
            // The remaining left parentheses are smaller than the right parentheses. The next parentheses can be either left or right
            if (left > 0) {
                getParenthesis(str + "(", left - 1, right);
            }
            getParenthesis(str + ")", left, right - 1); }}public static void main(String[] args) {
        System.out.println("===== Brute force method =====");
        List<String> strings = generateParenthesis(4);
        for (String string : strings) {
            System.out.println(string);
        }

        System.out.println("===== backtracking =====");
        List<String> strings1 = generateParenthesis2(4);
        for(String s : strings1) { System.out.println(s); }}}Copy the code

Ten thousand beautiful futures are not equal to a warm present.