조합합 II

40. 조합합II

난이도:중

주제: 배열, 역추적

후보 번호(후보)와 목표 번호(타겟)의 ​​집합이 주어지면 후보 번호의 합이 목표와 일치하는 후보에서 고유한 조합을 모두 찾습니다.

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

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

예 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
• 1

해결책:

역추적 접근 방식을 사용할 수 있습니다. 핵심 아이디어는 중복 항목을 쉽게 처리할 수 있도록 먼저 배열을 정렬한 다음 역추적을 사용하여 가능한 모든 조합을 탐색하는 것입니다.

이 솔루션을 PHP로 구현해 보겠습니다. 40. 조합합II

설명:

1. 정렬: 중복 항목을 쉽게 처리하고 조합이 정렬된 순서로 형성되도록 후보 배열을 정렬합니다.
2. 역추적: 역추적 기능은 가능한 모든 조합을 탐색하는 데 사용됩니다.
   • 타겟이 0이 되면 현재 조합을 결과에 추가합니다.
   • 현재 인덱스부터 시작하여 후보자를 반복합니다. 후보가 이전 후보와 동일할 경우 중복 조합을 피하기 위해 생략합니다.
   • 타겟에서 현재 후보를 빼고 새 타겟과 다음 인덱스를 사용하여 역추적 함수를 재귀적으로 호출합니다.
   • 유효한 조합을 찾거나 모든 가능성을 소진할 때까지 재귀 호출이 계속됩니다.
3. 가지치기: 후보자가 목표를 초과하면 추가 후보자도 목표를 초과하므로 루프에서 조기에 벗어납니다.

이 코드는 각 조합에서 각 후보가 한 번만 사용되도록 하면서 목표에 합산되는 모든 고유 조합을 출력합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 조합합 II의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!