题目

给出一个正整数n，请给出所有的包含n个'('和n个')'的字符串，使得'('和')'可以完全匹配。

例如：'(())()'，'()()()' 都是合法的； '())()('是不合法的。

输入描述:

输入为1个正整数

输出描述:

输出为所有合法的字符串，用英文逗号隔开

示例1

输入：2
输出：(()),()()

思路

回溯想了半天不对，过了 20% ，参考评论区大佬写的，本意也是深搜

import java.util.*;
import java.io.*;
class FindLegalStr {
    private static ArrayList<String> paths = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        solution(n, "", n, n);
        StringBuilder sb = new StringBuilder();
        for (String s : paths) {
            sb.append(s).append(",");
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    private static void solution(int n, String cur, int left, int right) {
        if (left == 0 && right == 0) {
            paths.add(cur);
            return;
        }
        if (left < 0 || right < 0 || left > right) {
            return;
        }
        solution(n, cur + "(", left - 1, right);
        solution(n, cur + ")", left, right - 1);
    }
}

总结

招行信用卡 2018 第二道
考的是对递归使用的功底了！因为知道递归深搜，却写不出来，这次收获一种写法，或许以后可以考虑一下左右两个变量来限制加入到结果集和的时机