括号生成

import java.util.ArrayList;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

/**

 * 思路：

 * 1：()

 * 2：从左到右插入 ()，得：(()) ()()

 * 3: 再次插入，去掉重复：(()()) ((())) (()()) | ()()()

 */

class Solution {

    public List<String> generateParenthesis(int n) {

        // 初始化一个括号

        List<String> result = new ArrayList<>();

        result.add("()");

        // 从第二个括号开始

        for (int i = 2;i <= n; i++){

            // 记录二个括号的所有结果

            Set<String> current = new HashSet<>();

            // 循环第一个括号的所有结果

            for (String res : result){

                // 对每一个结果，从左到右插入 ()

                for (int j = 0; j < res.length(); j++){

                    current.add(res.substring(0, j) + "()" + res.substring(j));

                }

            }

            result = new ArrayList<>(current);

        }

        return result;

    }

}

class Solution {

    public List<String> generateParenthesis(int n) {

        if (n == 1) return Arrays.asList("()");

        Set<String> result = new HashSet<>();

        for (String res : generateParenthesis(n - 1)){

            for (int i = 0; i < res.length(); i++){

                result.add(res.substring(0, i) + "()" + res.substring(i));

            }

        }

        return new ArrayList<>(result);

    }

}