후보 번호 집합(모든 요소가 고유함)과 대상 번호가 있다고 가정합니다. 후보 번호가 주어진 목표와 합해지는 후보에서 모든 고유한 조합을 찾아야 합니다. 동일한 반복 번호는 후보자 중에서 무제한으로 선택할 수 있습니다. 따라서 요소가 [2,3,6,7]이고 대상 값이 7이면 가능한 출력은 [[7], [2,2,3]]
입니다.단계를 살펴보겠습니다 -
-
우리는 이것을 재귀적으로 해결할 것입니다. 재귀 함수의 이름은 solve()입니다. 이것은 결과를 저장하기 위한 배열, 레코드를 유지하기 위한 하나의 맵, 대상 값 및 고유한 요소 목록을 사용합니다. 처음에는 res 배열과 맵이 비어 있습니다. 해결 방법은 아래와 같이 작동합니다 -
- 대상이 0이면
- temp :=목록에 있는 요소 목록
- temp1 :=temp, temp 정렬
- temp가 맵에 없으면 맵에 temp를 삽입하고 값을 1로 설정하고 temp를 res에 삽입
- 반환
- temp <0이면 반환
- i 범위의 x에서 요소 목록의 길이까지,
- 요소[x]를 현재에 삽입
- 해결(요소, 대상 – 요소[x], 해상도, 지도, i, 현재)
- 색인의 현재 목록에서 요소 삭제(현재 길이 – 1)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object):
def combinationSum(self, candidates, target):
result = []
unique={}
candidates = list(set(candidates))
self.solve(candidates,target,result,unique)
return result
def solve(self,candidates,target,result,unique,i = 0,current=[]):
if target == 0:
temp = [i for i in current]
temp1 = temp
temp.sort()
temp = tuple(temp)
if temp not in unique:
unique[temp] = 1
result.append(temp1)
return
if target <0:
return
for x in range(i,len(candidates)):
current.append(candidates[x])
self.solve(candidates,target-candidates[x],result,unique,i,current)
current.pop(len(current)-1)
ob1 = Solution()
print(ob1.combinationSum([2,3,6,7,8],10)) 입력
[2,3,6,7,8] 10
출력
[[2, 8], [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [3, 7]]