Concise code in Java

• My thought: To confirm to the limitation, we can construct a stack mentally. A '(' corresponds to push, while a ')' corresponds to pop. At this point, our mission is to push all '('s in to the stack and pop the stack until it's empty. Of course, the operations can interleave. I took a recursive way since it's straight forward that at each state, say m '(' waiting to be pushed and n '(' waiting to be popped, we can either push a '(' or pop a '('.

``````public class Solution {

List<String> ans = new ArrayList<String>();

public List<String> generateParenthesis(int n) {
dp(n, 0, "");
return ans;
}

public void dp(int outstack, int instack, String res) {
if(outstack == 0 && instack == 0) {
return;
}
if(outstack > 0) {
dp(outstack-1, instack+1, res+"(");
}
if(instack > 0) {
dp(outstack, instack-1, res+")");
}
return;
}

}
``````

However, I don't have a clue how to implement it iteratively :(

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• This wiki: https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics can provide you a iterative thought.

• Here is my iteratively solution. Based on Applications of Catalan Number in combinatorics

``````public class Solution {
private static final String UNIT = "()";
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<String>();
if (n == 0) return result;
Set<String> visited = new HashSet<String>();
Queue<String> queue = new ArrayDeque<String>();
while (!queue.isEmpty()) {
String s = queue.poll();
if (s.length() == n * 2)
else {
for (int i = 0; i <= s.length() / 2; i++) {
String news = s.substring(0, i) + UNIT + s.substring(i, s.length());
if (!visited.contains(news)) {