7299 : 재귀 심화 종합 1
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 서로 다른 정수에서 합이 정확히 $T$가 되는 부분집합 조합(중복 없이)을 모두 출력하십시오.
백트래킹으로 구현하며, 중복 원소가 있을 경우 동일한 조합이 여러 번 출력되지 않도록 처리합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
백트래킹으로 구현하며, 중복 원소가 있을 경우 동일한 조합이 여러 번 출력되지 않도록 처리합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원소의 개수 $N$과 목표 합 $T$가 주어집니다. ($1 \le N \le 20$, $1 \le T \le 1{,}000$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
첫째 줄에 조합의 수를 출력합니다.
이어서 각 조합을 오름차순으로 공백 구분하여 줄바꿈 출력합니다.
이어서 각 조합을 오름차순으로 공백 구분하여 줄바꿈 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
1 2 3 4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1 4
2 3
5도움
정렬 후
def backtrack(start, remain, path)를 구현합니다. 남은 합이 0이면 결과 추가, 현재 원소가 남은 합보다 크면 종료합니다.