[Leetcode] 39. Combination Sum

문제 바로가기

처음 풀이

최적화는 신경쓰지 않고 어떻게 풀지 생각하고 작성한 코드이다. 풀리긴했으나 매우 긴 수행 시간이 걸렸다.
Time Complexity: O(n^3 logn)

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

        def DFS(sum):
            remainder = target - sum
            if remainder == 0:
                print(stack)
                answer.add(tuple(sorted(stack)))
            elif remainder < 0:
                return

            for c in candidates:
                if c > remainder:
                    continue

                stack.append(c)
                DFS(sum + c)
                stack.pop()

        DFS(0)
        return list(list(tupl) for tupl in answer)

참고한 답안

candidates를 정렬하고 for문으로 candidates를 순회하면서 모든 경우를 한번씩만 지난다. -> set 필요 x
깊이 우선 탐색을 진행하면서 candidates와 target을 점점 줄여가면서 계산을 줄였다. -> 최적화
Time Complexity: O(n^2)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = list()
        
        def DFS(listCur, candidates, target):
            for i, cand in enumerate(candidates):
                rem = target - cand
                
                if rem == 0:
                    answer.append(listCur + [cand])
                elif rem > 0:
                    DFS(listCur + [cand], candidates[i:], rem)
                else:
                    break

        DFS([], sorted(candidates), target)
        
        return answer