[leetcode]Generate Parentheses
1421 ワード
簡単な問題.DFS.やはりJavaで関数を書くのは面倒です.最初はleft
import java.util.ArrayList;
public class Solution {
public ArrayList<String> generateParenthesis(int n) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<String> arr = new ArrayList<String>();
ArrayList<Character> chars = new ArrayList<Character>();
dfs(arr, 0, 0, chars, n);
return arr;
}
private void dfs(ArrayList<String> arr, int left, int right, ArrayList<Character> chars, int n)
{
if (left + right + 1 == n * 2)
{
if (left < right) {
// chars.add('(') - impossible
// chars.remove(chars.size() - 1);
}
else
{
chars.add(')');
StringBuilder sb = new StringBuilder();
for (char c : chars) {
sb.append(c);
}
arr.add(sb.toString());
chars.remove(chars.size() - 1);
}
}
else
{
if (left > right) {
chars.add(')');
dfs(arr, left, right + 1, chars, n);
chars.remove(chars.size() - 1);
}
if (left < n)
{
chars.add('(');
dfs(arr, left + 1, right, chars, n);
chars.remove(chars.size() - 1);
}
}
}
}