# Algorithms comparison and complexity

I want to sole this problem:

Write a method to return all valid combinations of n-pairs of parentheses.

The method should return an ArrayList of strings, in which each string represents a valid combination of parentheses.

The order of the strings in the ArrayList does not matter.

Examples: combParenthesis(2) ==> {"(())","()()"}

Note: Valid combination means that parentheses pairs are not left open. ")()(" is not a valid combination.

My first solution is:

``````public static ArrayList<String> combParenthesis2(int pairs) {
ArrayList<String> res = new ArrayList<String>();
recursive(pairs, pairs, "", res);
return res;
}

public static void recursive(int left, int right, String build, ArrayList<String> res) {
if(right == 0 && left == 0) {
return;
}

if(left > 0)
recursive(left-1, right, build + "(", res);

if(right > left)
recursive(left, right-1, build + ")", res);
}
``````

And I think the complexity is O(N^2), am I Wrong?

The second algorithm is:

``````public static ArrayList<String> combParenthesis(int pairs) {
Set<String> result = new HashSet<>();
if (pairs <= 0) {
return new ArrayList<>(result);
}

if (pairs == 1) {
return new ArrayList<>(result);
}

for (int i=1; i<pairs; i++) {
Set<String> newSet = new HashSet<>();
for (String s : result) {
}
result = newSet;
}

return new ArrayList<>(result);
}
``````

Which is the complexity of the second algorithm?
Which one do you prefer and why?