[JS] 코딩 테스트 문제 : 부분 집합 구하기 [DFS]

문제 : 부분집합 구하기(DFS)

문제 설명

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.

▣ 입력설명

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

▣ 출력설명

첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.

▣ 입력예제 1

3

▣ 출력예제 1

1 2 3
1 2
1 3
1
2 3
2
3

내코드

// 문제 해설 참고한 코드
function solution(n) {
  let answer = [];

  // 부분집합을 나타낼 str 매개변수를 빈 문자열로 초기화
  function DFS(L, str = "") {
    // 모든 원소를 거친 이후(현재 원소값 L 이 n 을 넘어가는 경우)에
    // 문자열이 비어있는 경우(공집합인 경우)를 제외하고 최종적으로 완성된 문자열을 배열에 추가하고 함수 종료
    if (L > n) return str && answer.push(str);

    // 현재 원소값 L이 포함된 부분집합의 경우로 L 값이 추가된 문자열 str 과 L + 1 인자로 재귀 함수 호출
    DFS(L + 1, str + L);

    // 현재 값 L 포함되지 않은 부분집합의 경우로 L 값이 추가되지 않은 문자열 str 과 L + 1 인자로 재귀 함수 호출
    DFS(L + 1, str);
  }
  DFS(1);
  return answer;
}

console.log(solution(3));

풀이

1. 현재 원소 값을 의미할 L 부분 집합을 나타낼 str 매개변수(빈 문자열로 초기화)를 가지는 재귀 함수를 선언
2. 현재 원소 값 L이 포함된 부분 집합의 경우로 L 값이 추가된 문자열 str 과 L + 1 인자로 재귀 함수 호출, 현재 값 L 포함되지 않은 부분 집합의 경우로 L 값이 추가되지 않은 문자열 str 과 L + 1 인자로 재귀 함수 호출
3. 모든 원소를 거친 이후(현재 원소값 L 이 n 을 넘어가는 경우)에 문자열이 비어있는 경우(공집합인 경우)를 제외하고 최종적으로 완성된 문자열을 배열에 추가하고 함수 종료

다른 해결 방법

// 정답지 방법
function solution(n) {
  let answer = [];
  // n + 1 길이의 체크 배열(ch)을 생성하고 0 으로 모두 초기화
  // (값이 0 : 원소가 부분집합에 있지 않은 경우, 값이 : 1 원소가 부분집합에 있는 경우)
  let ch = Array.from({ length: n + 1 }, () => 0);

  // 현재 원소 L 값이 현재 원소값 L 이 n + 1 이 되는 경우 재귀함수를 종료
  function DFS(L) {
    if (L === n + 1) {
      let tmp = "";

      // ch[L] 값이 1인 경우 그 배열의 인덱스값을 문자열(tmp)에 추가하며
      for (let i = 1; i <= n; i++) {
        if (ch[i] === 1) tmp += i + " ";
      }

      // 문자열이 비어있는 경우 즉 공집합인 경우를 제외하고 최종적으로 완성된 문자열을 배열에 추가
      if (tmp.length > 0) answer.push(tmp.trim());
    }
    // 체크 배열에 L번째(ch[L]) 값이 0인 경우와 1인 경우로 나누어 재귀 함수 호출
    else {
      ch[L] = 1;
      DFS(L + 1);
      ch[L] = 0;
      DFS(L + 1);
    }
  }
  DFS(1);
  return answer;
}

console.log(solution(3));

풀이

1. n + 1 길이의 체크 배열(ch)을 생성하고 0 으로 모두 초기화 (값이 0 : 원소가 부분집합에 있지 않은 경우, 값이 : 1 원소가 부분집합에 있는 경우)
2. 현재 원소 값을 나타내는 L 을 매개변수를 가지는 재귀 함수 DFㄴ 을 선언 체크 배열에 L번째(ch[L]) 값이 0인 경우와 1인 경우로 나누어 재귀 함수 호출
3. 현재 원소 L 값이 현재 원소 값 L 이 n + 1 이 되는 경우 재귀 함수를 종료 ch[L] 값이 1인 경우 그 배열의 인덱스 값을 문자열(tmp)에 추가
4. 문자열이 비어있는 경우 즉 공집합인 경우를 제외하고 최종적으로 완성된 문자열을 배열에 추가

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=64099