Java Recursive Solution


  • 3
    C

    Base case: return value is "()" if n == 1.

    Recursion: answer is the combination of "()" and generatePaenthesis(n - 1). In order to get that, for each string in the list, insert "()" in every position until the end.

    In order to eliminate duplicates, I use HashSet to store each element. Add all elements in set into list and return the list at last.

    public class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> result = new ArrayList<>();
            if (n < 1) return result;
            if (n == 1) {
                result.add("()");
                return result;
            }
            List<String> list = generateParenthesis(n - 1);
            Set<String> set = new HashSet<>();
            for (int i = 0; i < list.size(); i++) {
                String str = list.get(i);
                int length = str.length();
                for (int j = 0; j < length; j++) set.add(str.substring(0, j) + "()" + str.substring(j));
                set.add(str.substring(0) + "()");
            }
            result.addAll(set);
            return result;
        }
    }

Log in to reply
 

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