36. Combination Sum

🎯 leetcode - 39. Combination Sum

---

🤔 나의 풀이

📌 문제

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

📌 날짜

2020.02.05

📌 시도 횟수

1 try

💡 Code

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(curr, csum):
            if csum > target:  # csum이 target보다 크면 종료
                return
            if csum == target:  # 같으면 path를 results에 저장
                result.append(path[:])
                return

            for val in curr:
                path.append(val)
                dfs(candidates[candidates.index(val) :], sum(path))
                path.pop()

        path, result = [], []
        dfs(candidates, 0)
        return result

💡 문제 해결 방법

- curr : 현재 탐색을 시도할 list
- path : 탐색 경로를 담을 list. 
- csum : sum(path) / 만약 sum 값이 target이 되면 path를 result에 담는다.

- 순열과 조합을 적절하게 활용한 풀이이다.
- 다음 재귀때 탐색할 list를 전달할 때는 [현재인덱스부터 ~ 끝]까지의 list를 전달했다.
>> dfs(candidates[candidates.index(val) :], sum(path))
- 따라서 현재 인덱스를 포함시킴으로써 중복으로 사용이 가능하되, 만약 조건에서 벗어나면 
현재 for문을 break하여 다음 값으로 넘어갈 수 있게 하였다. 
- csum은 매번 sum(path)로 계산하기 싫어서 그냥 계산한 값을 전달하고자 넣었다.

⭐ 추가 설명

• 위 그림의 과정을 보면 이해가 잘 된다.
• candidates = [2, 3, 5, 6] / target = 8인 상황이다.
• 위 그림에서 . . .
  (O)는 코드의 if csum == target인 경우이고
  (X)는 코드의 if csum > target인 경우이다.
• (O),(X)가 나타날 때마다 탐색이 종료되고 다음 숫자로 넘어가는 것을 볼 수 있다.
• 즉 위의 과정을 코드로 나타내면, 현재의 탐색을 return하고 다시 for문으로 돌아가 다음 for문으로 넘어간 상태이다.

💡 새롭게 알게 된 점

- dfs에서 중복을 처리하는 방법을 알게 되었다.
- 중복을 허용하는 경우 어떻게 탐색을 종료할 수 있는지에 대해 알게 되었다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. DFS로 중복 조합 그래프 탐색

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(csum, index, path):
            if csum < 0:
                return
            if csum == 0:
                result.append(path)     # 이 코드에서는 따로 부모 함수의 공간에 path=[]를 
                return			# 생성하지 않았으므로 [:] 연산자를 사용하지 않아도 된다.

            for i in range(index, len(candidates)):
                dfs(csum - candidates[i], i, path + [candidates[i]])
                

        result = []
        dfs(target, 0, [])
        return result

💡 문제 해결 방법

✔ dfs(csum - candidates[i], i, path + [candidates[i]]) 설명
- csum : 합을 갱신해나간다. 초깃값은 target으로, 재귀 호출마다 현재 탐색 중인 값을 뺀 값으로 갱신된다.
- i : 앞에서 중복 사용이 가능하다고 했으므로 자기자신을 포함할 수 있도록 i를 전달한다.
이 i는 다음 재귀 호출 시 for문의 가장 첫번째 시작점이 된다. 
- path + [candidates[i]] : 탐색 경로를 새로 추가하여 전달한다.

✔ 기본적인 틀은 위의 내가 푼 방법의 풀이와 비슷한 것 같다ㅎ
- path를 내부적으로 처리헸다는 점(pop()할 필요가 없음)
- 문자열 슬라이싱 대신 인덱스로 처리하여 전달한 점
등이 차이점인 것 같다.
- 물론 아래 답안 코드가 훨씬 빠르다 😅😢

💡 새롭게 알게 된 점

-

---