48.부분집합 구하기 - DFS
Updated:
🔍 문제
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요
🔹 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다
🔹 출력 설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다
🔹 입력예제 1
3
🔹 출력 예제 1
1 2 3
1 2
1 3
1
2 3
2
3
📌 풀이
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n) {
let answer= [];
let ch = Array.from({length: n + 1}, () => 0); // check arr 생성 길이가 4인 모두가 0이 된거임
function DFS(v) {
if(v === n + 1) { // DFS 탐색 종료 될때
let tmp = "";
for(let i = 1; i <=n; i++) { // n 만큼 반복해서
if(ch[i] === 1) tmp += i + " "; // ch arr 에서 1이 포함된경우 tmp 의 누적
}
if(tmp.length > 0) answer.push(tmp.trim()); // 공란을 제외한 tmp 를 빈칸을 없애서 answer 에 push
}
else {
ch[v] = 1; // ch arr에 1을 포함시킨 경우
DFS(v + 1);
ch[v] = 0; // ch arr에 1을 포함시키지 않은경우
DFS(v + 1);
}
}
DFS(1);
return answer;
}
console.log(solution(3));
</script>
</body>
Leave a comment