40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/?envType=featured-list&envId=top-google-questions

input :

• candidates, target

output :

• candidates의 원소를 중복으로 사용하지 않고 target 값을 만들 수 있는 모든 경우를 반환하시오.

조건 :

---

Solution explain : Solution1

idea

• 중복되는 경우들을 제외하기 위한 조건이 필요하다.
• base case :

if sum > target: 
	return
if sum == target:
	ret에 추가
    return

• recursive : 현재 순회하고 있는 인덱스가 idx와 동일한 경우에는 바로 재귀를 수행,
  현재 순회하고 있는 인덱스가 시작점과 다르고, 그 원소의 값이 이전과 동일하다면 중복된 원소 값들을 가지는 집합이 나올 수 있어 제외함.

주의

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ret = []
        candidates.sort()
        
        def recursive(used, idx, sum):
            if sum > target:
                return 
            if sum == target:
                ret.append(used)
                return 
            
            for i in range(idx, len(candidates)):
                if i > idx and candidates[i] == candidates[i - 1]:
                    # 맨 처음 등장하는 i의 경우에는 언제나 재귀를 수행해줌.
                    # 그러나 그 이후에는 해당 값을 다시 확인하지 않기 위해.
                    # [1, 2, 2, 2]
                    # 0, 1, 2의 idx를 확인 하면 되지.
                    # 0, 1, 3의 경우는 안 해도 되니까 이를 판단하기 위한 조건임.
                    continue

                item = candidates[i]
                recursive(used + [item], i + 1, sum + item)
        
        recursive([], 0, 0)
        
        return ret