(java)leetcode-22

Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

문제 풀이 방향: 이 문 제 는 아마 재 귀적 으로 풀 면 풀 수 있 을 것 이다.
num 을 설정 합 니 다. string 에 '(' 를 추가 할 때 num + +, string 에 ')' 를 추가 할 때 num - - 를 추가 하기 때문에 num 의 크기 를 판단 해 야 합 니 다.num = = = 0 일 때 는 '(', num = = 2 * n - str. length () 일 때 는 ')' 만 추가 할 수 있 고, num 이 0 < num < 2 * n - str. length () 일 때 는 둘 다 추가 할 수 있다.이렇게 끊임없이 재 귀 하면 결 과 를 얻 을 수 있다.

public class Solution {
    public List generateParenthesis(int n) {
		List result = new ArrayList();
		if(n == 0)
			return result;
		getstring(0,0,"",2*n,result);
        return result;
    }
	public void getstring(int x,int num,String str,int n,List result)
	{
		if(x == n-1)
			result.add(str+')');
		else
		{
			if(num > 0)
				getstring(x+1,num-1,str+')',n,result);
			if(num < n-x)
				getstring(x+1,num+1,str+'(',n,result);
		}
	}
}