leetCode - Combinations

leetcode.com/problems/combinations

 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        
        def DFS(level, node, combination):
            combination.append(node)
            # for leaf
            if level == k - 1:
                combinations.append(combination[:])
                combination.pop()
                return
            for next_node in range(node + 1, n - k + level + 3):
                DFS(level + 1, next_node, combination)
            # for every backtracking except backtracking at leaf
            combination.pop()
            
        combinations = []
        
        for i in range(1, n + 1):
            combination = []
            DFS(0, i, combination)
        
        return combinations

 

1. 무슨 자료구조를 쓰든지 케이스 한두개를 가지고 그린 다음에 짜야 한다.

2. 트리 쓸 때 어떻게 가지가 그려지는지(이 문제의 경우에는 children의 범위가 parent + 1 이상 n - k + level + 2 이하) 정확히 파악해야 한다.

3. DFS 함수 내에서 리프에 도달했을 때의 조건은 앞에, 백트래킹할 때 수행되는 부분은 호출 이터레이션 뒤에 붙이는 것이 좋다. 즉, 

def DFS(level, node, record):
    # 1. record
    record(node)
    # 2. terminte at leaf (can be ommitted if iteration in 3. do nothing
    if node is leaf:
    	backtracking process(ex: delete last node from record)
    	return
    # 3. iteration of recursion
    for children of this node:
    	DFS(level + 1, child, record)
    # 4. backtracking process
    backtracking process(ex: delete last node from record)

이와 같은 구조를 띄는 것이 좋다.