[Algorithm] LeetCode 39. Combination Sum in Python

💡 LeetCode 39:

주어진 숫자들을 가지고 target을 만들 수 있는 모든 조합 찾기

🌱 코드 in Python

알고리즘: DFS

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        l = len(candidates)

        def dfs(i, s, tmp):
                if s == target:
                    ans.append(tmp)
                    return
                if s > target or i == l:
                    return
                if target - s < candidates[i]:
                    return
                tmp.append(candidates[i])
                dfs(i, s + candidates[i], tmp.copy())
                tmp.pop()
                dfs(i + 1, s, tmp.copy())

        candidates.sort()
        dfs(0, 0, [])

        return ans

평범한 dfs문제였는데 처음에 조금 헤맸던 부분은
같은 인덱스를 계속해서 탐색할 수 있는데 대체 어디서 인덱스를 늘려줘야 하지? 였다

처음에는 dfs안에 while문을 두고 돌릴까도 했는데,
역시 그건 아니었고 많은 고민끝에 넣은 코드가

if s > target or i == l

tmp.pop()
dfs(i + 1, s, tmp.copy())

이 두 부분이었다.
남들은 다 쉽게 푸는 것 같은데, 나는 왜 이렇게 이런 문제도 고전해야 하는 건지..
하지만 오늘 풀어봤으니!! 다음엔 좀 더 쉽게 할 수 있지 않을까..
하고 기대..!

if target - s < candidates[i]:

이 부분은 효율을 위해 추가한 부분.
더 넣어볼 필요가 없을 경우 재귀문을 빠르게 종료시키기 위해 넣었다.

🧠 기억하자

1. dfs 방식을 조금 더 잘 이해할 필요가 있다.

LeetCode 39 바로가기