[Recursive Questions] Print all combination of Parenthesis

Combination 문제는 Permutation 문제의 응용문제라고 할 수 있다. 재귀함수 호출에 의한 문제 풀이를 한번 알아보자.

문제: 괄호의 수를 의미하는 integer 값을 입력을 받아 가능한 괄호의 조합을 프린트해주는 함수를 짜보자. 예를 들어 3을 입력으로 넣었다면, ((())), (())(), ()(()), (()()), ()()() 문자열이 프린트 되어야 한다.

#Walk through
0. 함수의 인자 값으로 다음과 같이 받을 것이다. (leftRemain, rightRemain, str)
1. [Base condition] 만약 rightRemain의 수가 0이라면, str을 프린트한다.
2. 만약 leftRemain가 0보다 큰지 확인한다.
2-1-a. 크다면, leftRemain을 하나 줄인 다음 str에 “(“를 추가해서 재귀 함수를 호출하자.
2-1-b. 만약, leftRemain가 rightRemain 보자 작은지 확인하자.
2-1-b-i. 작다면, rightRemain을 하나 줄인 다음 str에 “)”를 추가해서 재귀 함수를 호출하자.
2-2. 작다면, rightRemain을 하나 줄인 다음 str에 “)”를 추가해서 재귀 함수를 호출하자.

  1. - (void)printAllCombinationOfParenthesisWrapper:(NSInteger)numberOfPar{
  2.     [self printAllCombinationWithLeftRemain:numberOfPar
  3.                                     rightRemain:numberOfPar
  4.                                          string: @""];
  5. }
  6.  
  7. - (void)printAllCombinationWithLeftRemain:(NSInteger)leftRemain
  8.                               rightRemain:(NSInteger)rightRemain
  9.                                    string:(NSString *)str{
  10.     if (rightRemain == 0){
  11.         NSLog(@"%@", str);
  12.         return;
  13.     }
  14.  
  15.     if(leftRemain != 0){
  16.         [self printAllCombinationWithLeftRemain:leftRemain-1
  17.                                     rightRemain:rightRemain
  18.                                          string: [str appendString:@"("]];
  19.         if(leftRemain < rightRemain){
  20.             [self printAllCombinationWithLeftRemain:leftRemain
  21.                                         rightRemain:rightRemain-1
  22.                                              string: [str appendString:@")"]];
  23.         }
  24.     }
  25.     else{
  26.         [self printAllCombinationWithLeftRemain:leftRemain
  27.                                     rightRemain:rightRemain-1
  28.                                          string: [str appendString:@")"]];
  29.     }
  30. }