-
[파이썬] 리트코드 39. Combination Sum 풀이기타/알고리즘 2020. 12. 24. 22:53반응형
Combination Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
candidates = [2,3,6,7] 와 같은 식으로 주어졌을 때, candidates안의 요소들을 더하여 target = 7을 만들 수 있는 배열을 출력하는 문제다.
그래프를 탐색하며 각각의 값들을 더해가다가 합한 값이 target이 되었을 때, 여태까지의 경로를 출력하면 되는 것이다.
1. dfs의 변수로 csum(target까지 남은 수), index, path를 이용한다
2. 만약 csum이 0보다 작으면 멈춘다(return).
3. csum이 0이 된다면 여태까지의 경로를 정답에 저장해준다
4. 그 이외의 경우에는 재귀를 이용해 탐색한다
- 인덱스에서 candidates의 길이 사이의 범위의 i에 대해
- csum에서 candidates[i]를 빼고, 인덱스를 i로 갱신하고, 경로에 [candidates[i]를 더한 dfs를 실행한다
5. dfs(target,0,[]) 실행. target이 0이 될 때까지 인덱스 0부터 빈 리스트 []에 경로를 저장해나갈 것이다
6. csum, 혹은 target이 0이 될 때의 경로들이 저장된 result를 출력해준다
class Solution: 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
반응형'기타 > 알고리즘' 카테고리의 다른 글
백준 파이썬 11722번 : 가장 긴 감소하는 부분 수열 풀이 (0) 2020.12.25 [파이썬] 리트코드 198. House Robber 풀이 (0) 2020.12.24 [파이썬] 리트코드 53. Maximum Subarray 풀이 (0) 2020.12.24 [파이썬] 리트코드 78. Subsets 풀이 (0) 2020.12.24 [파이썬] 다이나믹 프로그래밍 기초 (0) 2020.12.23