# Generate Parentheses

{% tabs %}
{% tab title="Java" %}
```java
class Solution {
		public List<String> generateParenthesis(int n) {
			List<String> result = ArrayList<String>();
			StringBuilder sb = new StringBuilder();
			DFS(n, 0, 0, 0, sb, result);
			return result;
		}
		private void DFS(int n, int start, int left, int right, StringBuilder sb, List<String> result) {
			if (n == 0 && left == right) {
				result.add(sb.toString());
				return;
			}
			
			for (int i = start; i < n; i++) {
				if (right > left) {
					break;
				} else if (left == right) {
					sb.append("(");
					left++;
					DFS(n--, i + 1, left, right, sb, result);
					sb.remove(sb.length - 1);
				} else { left > right && left < 2/n) {
					sb.append(")");
					right++;
					DFS(n--, i + 1, left, right, sb, result);
					sb.remove(sb.length - 1);
				}
			}
		}
}

```
{% endtab %}
{% endtabs %}
