[leet22] DFS 인자를 할당된 객체가 아닌 직접 지정해줘야 하는 경우

leetcode 22 Generate Parentheses

DFS에서의 변수 고정

나는 보통 DFS를 돌 때 아래와 같은 방식을 사용한다.
1. 체크할 변수에 root를 반영
2. root에서 다음 갈 수 있는 자리(togo) 선정
3. for loc in togo: 에 대해서 dfs 실행

def helper(path, root, cum):
    nonlocal ans, n
    if len(path)==n:
        ans.append(path)
        return
    path.append(root)
    cum += root
    if cum == 0: togo = [1]
    if cum == n: togo = [-1]
    else: togo[-1, 1]
    for loc in togo:
        dfs_helper(path, loc, cum) 

하지만 이렇게 되면 처음 리프로 다녀와서 두번째 리프를 찾아 나설 때, path가 이미 가득 차 있게 된다. 그렇다고 return 전에 path를 초기화하자니 다음 리프로의 탐색이 path=None 상태에서 다시 시작하는 것도 아니기 때문에 이렇게도 불가능하다.
이 문제에서는 이를 방지하기 위해 변수에 할당하지 않고 직접 재귀함수에 값을 넣어주었다. 한번 리프에 다녀오더라도 고정된 값에서부터 출발하기 때문에 원하는 탐색을 진행할 수 있게 된다.

if cum == 0:
            dfs_helper(str1+'(', cum+1)
        elif cum == n:
            dfs_helper(str1+')', cum-1)
        else:
            dfs_helper(str1+'(', cum+1)
            dfs_helper(str1+')', cum-1)

Question

n쌍의 괄호를 사용해서 유효한 모든 괄호문자 만들기

Solution

PSEUDO 1

• 맨 앞, 맨 뒤에 ( ) 을 각각 넣고 가운데 2n-2개 자리 중 n-1개를 뽑는 combinations 수행, '('가 들어갈 index를 구하는 작업
• pool (가능한 모든 샘플)
• pool의 모든 경우에 대해 isValid

Solution 1도 시간 제한 내에 통과하였으나 포스팅 길이가 길어지니 풀 코드는 아래 github에서 참고

PSEUDO 2

• DFS를 돌리는데, path나 cum에 값을 할당해주면 돌면서 계속 바뀌기 때문에 직접 함수에 집어넣는 형태로
  path += ')', cum -= 1처럼.

def sol_2(n):
    ans = list()
    def dfs_helper(str1, cum):
        nonlocal ans, n
        if len(str1) == n*2:
            if cum == 0:
                ans.append(str1)
            return
        
        if cum == 0:
            dfs_helper(str1+'(', cum+1)
        elif cum == n:
            dfs_helper(str1+')', cum-1)
        else:
            dfs_helper(str1+'(', cum+1)
            dfs_helper(str1+')', cum-1)
    dfs_helper(str(), 0)
    return ans