부분집합 구하기(DFS)

-입력

3

 

-출력

코드

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

        function DFS(v) {
          if (v === n + 1) {
            let temp = "";
            for (let i = 1; i < v; i++) {
              if (ch[i] === 1) temp += i + " ";
            }
            if (temp.length > 0) answer.push(temp.trim());
          } else {
            ch[v] = 1;
            DFS(v + 1);

            ch[v] = 0;
            DFS(v + 1);
          }
        }

        DFS(1);

        return answer;
      }

문제 설명

이 문제는 위 사진처럼 1부터 시작해서 그 숫자가 포함되었는지 안되었는지를 체크하면서 풀어야한다. 

입력 3이 들어오면 사진처럼 2^3개의 경우의 수가 생기게된다.

 

1. ch에는 0~n의 숫자가 들어있고 0번째 배열은 사용하지 않는다. 나머지는 값이 1이면 포함한다는 의미이고 0이면 포함하지 않는다는 의미이다.

2. DFS 함수

-(v === n+1)인 경우

이 경우에는 for문을 이용해서 ch 배열에서 값이 1인 것들은 temp에 저장을 해준다. 그리고 temp가 빈 공백이 아니라면 answer에 push한다. 이때 temp에서 맨 뒤 공백을 제거하기 위해서 trim 함수를 이용한다.

 

-v < n+1인 경우

이 경우에는 사진처럼 포함된 경우, 포함이 안된 경우를 줘야하기 때문에 ch[v] = 1, ch[v] = 0으로 하고 각각 다음 단계인 DFS(v+1)을 해준다.