Python Algorithm Q36

November 22, 2022

Q36 Combiantion Sum

Q

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Sample Input

Example 1

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3

Input: candidates = [2], target = 1
Output: []

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

1. My Own Solution

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

        def dfs(currentTarget: int, nowlist: List):
            if currentTarget == 0:
                tmp = sorted(nowlist)
                if tmp not in ans:
                    ans.append(tmp)
                return
            if currentTarget < 0:
                return

            for N in candidates:
                dfs(currentTarget-N, nowlist+[N])

        dfs(target, [])
        return ans

# test set        
a = Solution()
b = [2, 3, 5]
targ = 8
a.combinationSum(b, targ)

딱 생각난대로 써낸 풀이이다. 얘도 DFS 형식으로 짜서 target에서 뺀 새로운 target을 다음 재귀로 전달하는 것을 반복하고, 0이 되면 append, - 가 되면 실패로 return을 만들었다. 여기까지만 해도 완벽했는데 치명적인 문제가 있었으니.. 바로 순서만 다른 중복값들을 쳐낼 수가 없다는 것이다. 35번 조합 문제에서는 애초에 원소들을 한 번씩만 고를 수 있었기 때문에 한번 골랐으면 다음 index로 넘어가게 하면 중복이 발생하지 않았는데 얘는 여러 번 선택할 수 있으니까 어디선가 중복이 발생한다… 그래서 진짜 단순무식하게 ans에 append하기 전에 sorted 하고 ans에 없는 경우에만 append하도록 했다. 이러니까 다행히 통과하긴 했는데 list를 매번 정렬해야하니까 시간이 당연히 뭉텅뭉텅이로 먹는다. 아무튼 간에 생각난대로 써도 답이 잘 나오니까 DFS 파트는 기분이 좋긴 하다.

2. Given Solution

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

        def dfs(csum, index, path):
            if csum < 0:
                return
            if csum == 0:
                result.append(path)
                return
                
            for i in range(index, len(candidates)):
                dfs(csum - candidates[i], i, path + [candidates[i]])

        dfs(target,0, [])
        return ans

책에서 주어진 답안의 핵심은 바로 현재 element를 골수까지 빨아먹고, 다음 step으로 넘어간다는 점이다. 예를들어 2, 3, 5로 8을 구성한다고 했을 때 처음 2로 시작한 loop에서 2가 들어간 모든 set을 싹-다 test하고, 그 뒤 3으로 시작한 루프에서는 아예 2 자체를 쓰지 못하게 만드는 것이다. 그러기 위해서 내 함수와는 다르게 index라는 인자를 하나 더 받는 것이다. candidates[]에서 0 번째 element(=2)로 가능한 한 모든 set을 다 test하며 이제 2는 이후의 set에서 영영 배제하는 것이다. 말그대로 DFS인 셈이다. 2라는 인자의 깊이 끝까지 다 들어갔다 나오니까 말이다. 이래서 중복이 안 생기는거구나…

Overall Review

DFS 파트에서 처음에 섬 개수 구하는 문제 푼 이후로 내가 생각하는 대로 코드를 썼더니 대부분 다 풀려서 DFS 파트에 자신감이 좀 생겼었는데 책에서 주어진 풀이를 보면서 아직 사고방식이 온전히 바뀌진 않았다는 것을 깨달았다. DFS 알고리즘을 이해는 했어도 사고방식은 아직 linear하구나… 반성해야겠다.

Hyuntae H