Very easy iterative Java solution using Set


  • 0

    I think I'm not smart enough to figure out an approach or others why there won't be missing or duplicate. Here is the code when I thought about this problem totally by myself. Just insert parentheses into each possible position and de-duplicate by HashSet. Sound a little stupid...

        public List<String> generateParenthesis(int n) {
            Queue<String> queue = new LinkedList<>();
            Set<String> result = new HashSet<>();
            queue.offer("");
            while (n-- > 0) {
                result.clear();
                for (int size = queue.size(); size > 0; size--) {
                    String par = queue.poll();
                    for (int i = 0; i <= par.length(); i++) {
                        String newpar = par.substring(0, i) + "()" + par.substring(i);
                        if (result.add(newpar))
                            queue.offer(newpar);
                    }
                }
            }
            return new ArrayList<>(result);
        }
    

Log in to reply
 

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