[LeetCode] 0040. 조합합 II

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

후보 번호 모음이 주어지면 (후보자) 및 대상 번호(목표), 다음에서 모든 고유한 조합을 찾습니다. 후보자 여기서 후보자 번호의 합은 다음과 같습니다. 목표.

각 숫자는 후보자 만 사용할 수 있습니다 한 번 조합에서.

메모: 솔루션 세트에는 중복된 조합이 포함되어서는 안 됩니다.

예시 1:

입력: 후보 = [10,1,2,7,6,1,5], 대상 = 8
산출: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

예 2:

입력: 후보 = [2,5,2,1,2], 대상 = 5
산출: 
[
[1,2,2],
[5]
]

제약:

1 <= 후보.길이 <= 100
1 <= 후보자[i] <= 50
1 <= 대상 <= 30

파이썬

				
					# 시간 복잡도: O(2^n) # 공간 복잡도: O(n) 입력 가져오기 목록 클래스 솔루션: def 조합Sum2(self, 후보자: List[int], 대상: int) -> List[List[int]] : 답변 = [] 후보자.sort() self.backtrack(candidates, target, 0, [], 답변) 답변 반환 def backtrack(self, 후보자, 대상: int, totalIdx: int, 경로: List[int], 답변 : List[int]): target < 0인 경우: target == 0인 경우 반환: Answer.append(path) return for i in range(totalIdx, len(candidates)): if i > totalIdx 및 후보자[i] == 후보자[i - 1]: 계속 self.backtrack( 후보자, 대상 - 후보자[i], i + 1, 경로 + [후보[i]], 답변, ) 후보자 = [10, 1, 2, 7, 6, 1, 5] target = 8 print(Solution().combinationSum2(후보, 대상))

중간

파이썬

관련 기사