항해99 알고리즘 7회차

조합의 합 https://leetcode.com/problems/combination-sum

Combination Sum - LeetCode

 

접근 방식

큐로 만들어서 제일 앞 순서를 지우면서

남은 값들을 더 해주고 타겟과 일치하면 result에 넣을려고 했다.

 

여기서 문제점은 중복된 값도 가능하다는 점

- 이 부분은 앞 순서를 지운거를 한번 더 더해주고 나눠서 추가를 해줄려고 했다.

 

놓친 점

중복 된 값이 가능하다는건 자기 자신만 더 하면서도 가능 해야한다.

이 부분을 놓쳤다.

 

DFS, BFS를 활용하지 못했다는 생각이 든다.

 

틀린 결과 

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    queue = collections.deque(candidates)
    result = []
    while queue:
        node = queue.popleft()

        # 타겟이랑 같으면 넘긴다.
        if node == target:
            result.append([node])
            continue

        # 타겟보다 크면 넘긴다.
        if node > target:
            continue

        store_node = node
        while node < target:
            for remaing_node in queue:
                if node > store_node:
                    new_node = [int(node / store_node) for i in range(2)]
                else:
                    new_node = node

                arr = [new_node] + [remaing_node]

                plus_result = node + remaing_node
                if plus_result == target:
                    result.append(arr)

            node = node + store_node

    return result

 

맞은 결과 - 파이썬 알고리즘 인터뷰

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

    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 result

---