Skip to content

Instantly share code, notes, and snippets.

@anil477
Created January 30, 2022 06:53
Show Gist options
  • Save anil477/e72e02351a5b108940bb963d9cc81a77 to your computer and use it in GitHub Desktop.
Save anil477/e72e02351a5b108940bb963d9cc81a77 to your computer and use it in GitHub Desktop.
22. Generate Parentheses
class Solution {
// 22. Generate Parentheses
// https://leetcode.com/problems/generate-parentheses/
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, new StringBuilder(), 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max){
if (cur.length() == max * 2) {
ans.add(cur.toString());
return;
}
if (open == close) {
backtrack(ans, cur.append("("), open+1, close, max);
cur.deleteCharAt(cur.length() - 1);
return;
}
if ((open+1) <= max) {
backtrack(ans, cur.append("("), open+1, close, max);
cur.deleteCharAt(cur.length() - 1);
}
if ((close+1) <= max) {
backtrack(ans, cur.append(")"), open, close+1, max);
cur.deleteCharAt(cur.length() - 1);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment