Subset (DFS)

06 Aug, 2021

Problem

Given a natural number N, write a program that prints all subsets of a set with elements 1 through N.

input

The first line is given a natural number N (1<=N<=10).

output

From the first line, the subsets are printed in the same order as in the output example below, one for each line
However, empty sets are not output

Solution

function solution(n) {
	let answer = [];
	let ch = Array.from({ length: n + 1 }, () => 0);

	function DFS(v) {
		if (v > n) {
			let tmp = '';

			for (let i = 1; i <= n; i++) {
				if (ch[i] === 1) tmp += i + ' ';
			}
			if (tmp.length > 0) answer.push(tmp.trim());

			console.log(tmp);
		} else {
			ch[v] = 1;
			DFS(v + 1);
			ch[v] = 0;
			DFS(v + 1);
		}
	}
	DFS(1);
	return answer;
}
rn answer;
}