👀 문제
https://leetcode.com/problems/generate-parentheses/
👊 도전
1. 설계
- 백트래킹(모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때 만이다)으로 모든 경우를 구한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
*
* @author HEESOO
*
*/
class Solution {
int N;
ArrayList<String> list;
public List<String> generateParenthesis(int n) {
N=n; // 메소드 파라미터로 넘기지 않고 전역변수로 사용하기 위함
list=new ArrayList<>();
backtracking(0, 0, "");
return list;
}
public void backtracking(int open, int close, String str){
if(open==N && close==N){ // 종료 조건
list.add(str);
return;
}
if(open<N){ // 아직 open을 다 사용하지 않은 경우
backtracking(open+1, close, str+"(");
}
if(close<N && open>close){ // close를 사용할 수 있는 경우
backtracking(open, close+1, str+")");
}
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 백트래킹으로 경우의 수를 구한다
- 재귀를 계속 호출하여 str를 만든다.
- 이때 종료 조건은 open(여는 괄호)과 close(닫는 괄호)를 각각 n번 쓴 경우이다.
- 종료 조건에 들어오면 str 생성이 완료된 것이므로 list에 넣고 종료한다.
- 아직 종료 조건이 아니라면 open과 close의 개수를 체크한다.
- open은 N개 사용해야 한다. 아직 사용하지 않았다면 (를 str에 추가한다.
- close는 open 개수에 따라 사용 여부가 결정된다. 현재까지 open이 close보다 많이 사용된 경우에만 close를 사용할 수 있다. close가 open 보다 더 많다면 조건을 만족하지 않는다.