[Leetcode 40] - Combination Sum II w/ Python

 

Given a collection of candidate numbers (candidates) and a target number (target), find all unique 

combinations in candidates where the candidate numbers sum to target. 

 

Each number in candidates may only be used once in the combination. 

 

Note: The solution set must not contain duplicate combinations.

 

 

 

숫자들로 이루어진 배열과 목표 (타겟) 숫자가 주어진다

배열들에 있는 숫자 합으로 목표에 도달할 수 있는 조합을 찾는 문제

배열에 있는 숫자는 한번씩 사용 가능하고 같은 조합을 리턴할 수 없다

 

 

 

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

 

 

---

 

 

 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

 

 

 

Example 2:

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

 

 

 

---

 

 

백트래킹으로 문제를 풀었다

 

1. 각 숫자에 도달할때 target에서 값을빼서 0에 도달했을때 현재 stack을 저장하는 방식을 구현

2. 만약 목표 숫자를 넘었을때는 바로 return해서 다음 값 확인

3. check로 현재 숫자와 같은 숫자가 배열에 또있다면 continue해서 한번만 확인하도록 작성

※ 각 함수마다 현재의 stack과 target 값이 달라지기 때문에 다음 함수로 넘어갈때 보내야된다

 

class Solution:
    def combinationSum2(self, candidates, target):
        c = sorted(candidates)
        ans = []

        def backtrack(index, newTarget, stack):
            if newTarget == 0:
                ans.append(stack.copy())
                return
            if newTarget < 0:
                return
            
            check = -1
            for i in range(index, len(c)):
                if c[i] == check:
                    continue
                stack.append(c[i])
                backtrack(i + 1, newTarget - c[i], stack)
                stack.pop()
                check = c[i]
            return
        
        backtrack(0, target, [])
        return ans

 

 

 

ㄴㅇㅅ

 

 

---

 

 

 

다른 사람의 코드도 읽어 봤을때 while loop으로 중복되는 숫자를 넘기는 방식도 있다

구현 자체는 비슷해서 참고용으로 작성

 

 

class Solution:
    def combinationSum2(self, candidates, target):
        c = sorted(candidates)
        ans = []

        def dfs(index, stack, currSum):
            if currSum == target:
                ans.append(stack.copy())
                return
    
            if index == len(c) or currSum > target:
                return

            stack.append(c[index])
            dfs(index + 1, stack, currSum + c[index])

            while index+1 < len(c) and c[index] == c[index+1]:
                index += 1

            stack.pop()
            dfs(index + 1, stack, currSum)

        dfs(0, [], 0)
        return ans