7282 : 재귀 부분집합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
재귀(백트래킹)를 이용하여 $N$개의 정수 집합의 모든 부분집합을 출력하십시오.
공집합은 제외하며, 원소 수가 적은 순서로, 같은 수이면 원소 값 기준으로 정렬하여 출력합니다.
총 $2^N - 1$개의 부분집합이 출력됩니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
공집합은 제외하며, 원소 수가 적은 순서로, 같은 수이면 원소 값 기준으로 정렬하여 출력합니다.
총 $2^N - 1$개의 부분집합이 출력됩니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 집합의 크기 $N$이 주어집니다. ($1 \le N \le 8$)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
공집합을 제외한 모든 부분집합을 원소 수 오름차순으로 줄바꿈 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1 2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
2
3
1 2
1 3
2 3
1 2 3도움
비트마스크를 이용하면 $\text{mask} = 1$부터 $2^N - 1$까지 순회하며 모든 부분집합을 열거할 수 있습니다. 또는 재귀적으로 각 원소를 포함/미포함으로 분기합니다.