[DFS, 백트래킹] Combination Sum

Combination Sum - LeetCode

def combinationSum(candidates, target):
    def dfs(tot, index, path):
        if tot == target:
            result.append(path[:])
            return
        if tot > target:
            return
 
        for i in range(index, len(candidates)):
            # print(f'dfs({tot + candidates[i]}, {i}, {path + [candidates[i]]})')
            dfs(tot + candidates[i], i, path + [candidates[i]])
 
    result = []
    dfs(0, 0, [])
    return result

---

dfs 문제는 풀기 전 항상 그림을 그려서 구조를 파악하자. 이 문제에 경우 2 3 5 7을 계속 가지 형태로 그려보면 도움이 된다. 자식 노드로의 이동은 dfs를 통해 발생하고, retrun을 만나면 for문을 통해 동일한 레벨의 노드를 탐색한다.

dfs(index +, path +)처럼 파라미터로 값을 넘기면 dfs가 리턴됐을 원상복귀가 되어있다. 파라미터로 값을 넘기자.