[LC] 39. Combination Sum

[seungriyou]

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

Approach

backtracking으로 접근한다.

이때, 주어진 candidates는 unique 원소로 이루어져있으며, 각 원소를 선택할 수 있는 횟수는 무제한이므로, recur 부분을 작성할 때 for i in range(idx, len(candidates))와 같이 시작 idx 부터 순회하면 된다.

또한, 매번 base condition 검사 시마다 sum(tmp)을 하는 것은 time 측면에서 좋지 않으므로, tmp_sum이라는 변수로 tmp의 합을 트래킹한다.

Complexity (?!)

잘 모르겠다.. (ref)

• Time: O(2^n)
• Space: O(2^n)