39. Combination Sum

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

input :

• candidates, target

output :

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

조건 :

• 반환 값을 이루는 집합들은 독립적이다.

---

Solution explain : Solution1

idea

• 재귀를 통해 만들 수 있는 모든 경우를 제작한다.
• base case: if remain < 0: return, if remain == 0: 답에 추가; return.
• recursive case : 반복문을 수행하면서 사용할 수 있는 원소들을 모두 사용한다.
• 사용의 의미는 target값에서 제거하고, 사용했다는 의미로 해당 원소를 추가하면서 함수를 수행하는 것이다.

주의

• 정답을 이루는 집합이 독립적이어야 하기에 idx를 저장해가며 이미 썼던 원소는 나중에 쓰지 않도록 하자.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = []
        def recursive(remain, idx, ret):
            if remain < 0:
                return
            
            if remain == 0:
                answer.append(ret)
                return
            
            for idx in range(idx, len(candidates)):
                recursive(remain - candidates[idx], idx, ret + [candidates[idx]])
            return

        recursive(target, 0, [])
        return answer