[LeetCode]Combination Sum

https://leetcode.com/problems/combination-sum/description/

Combination Sum - LeetCode

 

문제 분석

주어진 숫자를 더해서 target 값을 만들어 낼 수 있는 숫자 조합을 찾는 문제입니다. 주어진 숫자는 무제한으로 사용이 가능합니다.

 

처음 시도한 답안

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = []
        
        def dfs(idx, after_sub, path):
            # 차감한 값이 음수가 된다면 선택하지 않고 반복 종료.
            if after_sub < 0:
                return

            # 차감한 값이 0이라면(=path를 더한 값이 target) target을 고른 값들을 정답에 포함시키고 반복 종료.
            if after_sub == 0:
                answer.append(path)
                return

            # 중복으로 candidate를 고를 수 있기에 반복문에서 dfs 수행.            
            for idx in range(idx, len(candidates)):
                # target 값 - candidates[idx] 값을 빼고, 선택한 path 전달.
                dfs(idx, after_sub - candidates[idx], path + [candidates[idx]])

        dfs(0, target, [])

        return answer

접근 방법

1. dfs를 통해 숫자 조합을 찾습니다.
2. 숫자를 중복되게 이용할 수 있으므로 dfs 내부에서 반복문을 통해 dfs를 재귀적으로 호출합니다.
3. 만들어야하는 target 값에서 선택된 candidate 값을 차감하면서 0이 되는 숫자 조합은 answer에 추가합니다.
4. 만약 음수가 된다면, 해당 숫자 조합으로는 target을 만들어 낼 수 없다는 뜻이므로 return 합니다.
5. dfs의 인자로는 idx, target - 선택된 숫자, path를 넣습니다.
   1. idx를 받는 이유는 순서만 다른 조합을 제거하기 위함입니다. idx 이전에 위치한 숫자는 무시하도록 합니다.
   2. 부가 설명 : 2(idx=0)로 만들수 있는 경우의 수가 끝나면, 3으로 시작되는 경우의 수에서는 2(idx=0)는 무시합니다.
      이렇게 중복된 조합을 제거할 수 있습니다.

DFS의 알고리즘을 사용해 풀이할 수 있습니다. 사실 문제를 처음 접했을 때 DFS를 사용할 수 있다는 추측을 하지 못했습니다. 그래서 주어진 숫자들을 이용해서 트리 형태로 그림을 그려보니 추측할 수 있었습니다.

 

두번째로 시도한 답안 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = []
        candidates_length = len(candidates)
        
        def dfs(idx, sum_, path):
            # 더한 값이 target 보다 커지면 해당 숫자 조합은 선택하지 않고 반복 종료.
            if sum_ > target:
                return

            # 더한 값이 target 과 일치한다면 해당 숫자 조합을 정답에 추가하고 반복 종료.
            if sum_ == target:
                answer.append(path)
                return

            # 중복으로 candidate를 고르게 하기 위해 반복을 통해 dfs 수행.
            for idx in range(idx, candidates_length):
                # 사용한 숫자의 값을 더하고, 선택한 path 전달.
                dfs(idx, sum_ + candidates[idx], path + [candidates[idx]])

        dfs(0, 0, [])

        return answer

접근 방법

1. 기본적인 풀이는 첫번째와 모두 동일합니다.
2. 한가지 다른 점은 이해하기 쉽도록 sum_을 활용해 target 값을 넘어가는 경우에는 무시하도록 한 것입니다.