❌

문제36: 조합의 합

Created

Feb 12, 2023 06:13 AM

Tags

문제

숫자 집합 canditates를 조합하여 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열가능하다.

입력


[2,3,6,7], target = 7
[2,3,5], target = 8

출력


[
	[7],
	[2,2,3],
]
[
	[2,2,2,2],
	[2,3,3],
	[3,5],
]

풀이

재귀 풀이

정렬되어 있는지 여부 확인


results = []

def dfs(target, index, path):
	if target < 0:
		return
	if target == 0:
		results.append(path)
		return

	for i in range(index, len(candidates)):
		dfs(target - candidates[i], i, path+[candidates[i]])

dfs(target, 0, [])
return results

새로운 개념