리트코드 39번 Combination Sum (python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = list()

        def dfs(n_list: List[int], nums):
            if sum(n_list) == target:
                answer.append(n_list)
                return

            elif sum(n_list) > target:
                return

            for i, n in enumerate(nums):
                dfs(n_list + [n], nums[i:])

        for idx, num in enumerate(candidates):
            dfs([num], candidates[idx:])

        return answer

탐색을 할 때 현재의 원소보다 같거나 큰 원소만 탐색을 하도록 하였다. 즉, 현재 i번째 숫자로 탐색하였으면 이 다음은 i번째부터 그 뒤의 원소만 탐색하였다. 이를 통해 중복되는 탐색의 수를 줄일 수 있다.

Reference

파이썬 알고리즘 인터뷰 36번