문제
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요.
[입력설명]
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
[출력설명]
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.
입력예제 1
3
출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3
문제 풀이
예습 이론
- 이 문제와 같은 출력은 아래의 구조로 풀이할 수 있다.
- 부분집합의 개수는
2^n(공집합 포함)이다. 이 문제에서는 공집합을 제외하기 때문에2^n-1이다.
이 문제에서는 전체집합이 {1, 2, 3}이고, 공집합을 제외한 부분집합의 수는 2^3-1=7개이다. trim()메소드는 문자열 양 끝의 공백을 제거한다.
코드
- v를 포함시키는경우, 포함시키지 않는 경우로 나누어 문제를 풀 수 있다.
- ch배열에는 만약 1을 넣으면 ch[1]=1, 2를 넣으면 ch[2]=2를 넣기와 같은 용도로 사용된다. 이후 ch배열에서 1인 것만 출력한다.
- 종료되는 시점은 v===n+1일때이다. 이 때 answer에 tmp의 값을 push한다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n){
let answer=[];
let ch=Array.from({length:n+1}, ()=>0); //ch는 길이가 n+1이고 0으로 초기화된 배열
//v를 부분집합에 참여시키겠다 or 시키지 않겠다
function DFS(v){
if(v===n+1){ //부분집합 종료
let tmp=""; //반드시 여기서 초기화
for(let i=1; i<=n; i++){
if(ch[i]===1) tmp+=i+" ";
}
//공집합 제거 후 출력(tmp.length>0)
if(tmp.length>0) answer.push(tmp.trim()); //trim을 사용해서 양끝 공백을 제거
}
else {
//v를 포함 시키는 경우
ch[v]=1;
DFS(v+1); //왼쪽으로 뻗음
//v를 포함 시키지 않는 경우
ch[v]=0;
DFS(v+1); //오른쪽으로 뻗음
}
}
DFS(1);
return answer;
}
console.log(solution(3));
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/17