[LeetCode#22]Generate Parentheses
4938 단어 LeetCode
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
My analysis:
The key properity behind this problem is :
At each position, we could place '(' or ')'. And, we should place 6 brackets in total.
In fact, we follow the same pattern at each position to decide to place a '(' or ')'.
So, why not use recursion to solve this problem? We should try to figure out base cases and violation condition.
1. we must place three '(' brackets and three ')' brackets.
2. when the remained right brackets greater than the remained left bracket, the violation happens. (we should stop the recursion along this path.)
Base case: both three '(' and three ')' were placed.
Violation case: remainded right brackets > reamined left brackets ===> (())) The valid placement could not in it.
Skills in implementing recursion:
1. only when reaching the base case, we insert the answer of this recursion path.
2. In Java, the String is passed by reference. However, the String is immutable, if we try to change the String, we would create a copy of the String. The original String would keep the same. The net effect is equal to pass the String by value. (This properity makes it is quit useable for writing recursion)
if (l > 0) //at each position, we could add "(" or ")". for the same ans, we choose!
helper(l - 1, r, ans + "(", ret);
if (r > 0)
helper(l, r - 1, ans + ")", ret);
Apparently, the value of ans at the same layer would keep the same for both choice.
/*
recursion is very important!!! understand it !!!
1. what's the recursion rule? at each position, we add "(" or ")"
2. what's the base case? l == 0 and r == 0
3. what's the violation case? the existed left brackets larger than right brackets
*/
public class Solution {
public ArrayList<String> generateParenthesis(int n) {
ArrayList<String> ret = new ArrayList<String> ();
if (n == 0)
return ret;
helper(n, n, new String(), ret);
return ret;
}
static public void helper(int l, int r, String ans, ArrayList<String> ret) {
if (l > r)
//this is very important!!! the remained left parenthesis should larger than that of right. ((()))) it's invalid
return;
if (l == 0 && r == 0)
ret.add(ans);
if (l > 0) //at each position, we could add "(" or ")". for the same ans, we choose!
helper(l - 1, r, ans + "(", ret);
if (r > 0)
helper(l, r - 1, ans + ")", ret);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.