[LeetCode] 39. Combination Sum

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

Algorithm

개인적으로 많이깨달은 문제이므로 기록을 상세히 남긴다.

경우의 수....? 이진트리 백트래킹! 🧐

처음 생각한 풀이는 완전탐색이다. 아주원시적으로...아래 첫번째 트리 그림처럼 모든 경우 수를 탐색한다. 그리고 [2,2,3] [2,3,2]는 같은 것이니 정렬후 같은 리스트는 지워준다.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(s,path):
            tmp = sum(path)
            if tmp == target: # 정답조건
                answer.append(path[:])
            elif tmp > target: # 종료조건
                return
            
            for i in range(len(candidates)):
                path.append(candidates[i])
                dfs(s + 1, path)
                path.pop()

        answer = []
        dfs(0,[])

        result = []
        for sub in answer:
            sub = sorted(sub)
            if sub not in result:
                result.append(sub)

        return result

찬란한 효율 꼴등...

손쉽게 통과! ^ㅁ^..라고 좋아하면 안된다. 결국 내풀이는 모든 중복도 트리에서 세는거라 ㅋㅋ효율 저세상이다 OTL

그래서 이렇게 풀면안된다 ㅋ..

 

이제 맨 위 그림에서 두번째 트리그림을 보자.

여기서 핵심은, 트리 좌,우측을 절대 중복되지 않는 두개의 상태로 나누는거다! 그래서 중복을 트리에 포함해 재탐색하지않게...하는게 포인트다.

예를들어 2가 두개이상 / 2가 한개인 path...자 여기서 그럼, 어떻게 이러한 상태를 정확히 나눠갈까? 아래그림을 보자.

위를 보면 i라는 포인터를 둔다. i 는 쉽게말해 path에 가능한 노드 후보값을 지정하는것이다. i 이상 인덱스값이 후보군이라 보면된다.

위에서 [2] 인 상태를 보면, 경로에 2가 두개이상 포함되는경우([2,2]) 2가 한개포함되는 경우([2]) 로 나뉜다.근데 여기서 주의할점은, 2가 한개 포함되는경우에는 2가 더이상 포함되면 안된다!백트래킹으로 2가 두개이상인경우를 모두 탐색하고, i+1을 통해 2를 후보에서 제외해준다.

 

요약하면, 이 알고리즘은 후보값을 중복없이 탐색하기 위해 인덱스 포인터인 i를 사용한다. 따라서 백트래킹을 사용하여 2가 두 개 이상인 경우를 모두 탐색하고,,,i+1을 통해 2를 후보에서 제외해 주는 것이다!

 

와우...정말 좋은 문제였다 캬 분발하자 나자신,,,

---

Python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(i, path, total):
            # 정답조건
            if total == target:
                res.append(path.copy())
                return
            # 종료조건
            if i >= len(candidates) or total > target:
                return
            
            # 탐색
            path.append(candidates[i]) # 현재값 경로 리스트에 추가
            dfs(i, path, total + candidates[i]) # 현재값 포함
            path.pop()
            dfs(i + 1, path, total) # 현재값 미포함

        res=[]
        dfs(0,[],0)
        return res

Java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList();
        dfs(candidates, target, ans, path, 0);
        return ans;
    }

    public void dfs(
        int[] candidates, 
        int target, 
        List<List<Integer>> ans, 
        List<Integer> path,
        int i
    ){
        if(target == 0){
            ans.add(new ArrayList(path));
        } else if (target < 0 || i >= candidates.length){
            return;
        } else {
            path.add(candidates[i]);
            dfs(candidates, target-candidates[i], ans, path, i);
            path.remove(path.get(path.size()-1));
            dfs(candidates, target, ans, path, i+1);
        }
    }
}