Java Solution (8 ms) using HashSet

  • 2

    I won't claim that this is efficient, but it does run a lot faster than I expected it to. I was having trouble coming up with a better recursive solution, so I did this: for each pattern of (n-1) parenthesis, insert an "()" at each position and each new pattern to a HashSet. If the pattern was already in the HashSet, ignore it and continue.

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if(n <= 0) return result;
        if(n == 1) {result.add("()"); return result;}
        StringBuilder sb = new StringBuilder();
        HashSet<String> hashSet = new HashSet<>();
        List<String> prev = generateParenthesis(n-1);
        for(String s : prev) {
            for(int i = 0; i <= s.length(); i++) {
                sb.insert(i, "()");
                if(!hashSet.contains(sb.toString())) {
        return result;

  • 0

    Similar thought except I do it iteratively. For your reference:

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.