부분집합 구하기 : DFS

내 풀이

function solution(n) {
  let answer = [];
  function DFS(k, str) {
    if (k > n) {
      answer.push(str.trim());
      return;
    }
    DFS(k + 1, str + k + ' ');
    DFS(k + 1, str);
  }
  DFS(1, '');
  return answer;
}

console.log(solution(3));

Solution보다 내 풀이가 훨씬 간결하고 깔끔한 것 같다.
(구현 idea는 동일함)

Solution 풀이

let answer = [];
let arr = Array.from({ length: n + 1 }, () => 0);
function DFS(k) {
  if (k > n) {
    let temp = '';
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] === 1) temp += i + ' ';
    }
    if (temp.length > 0) answer.push(temp.trim());
    return;
  }
  arr[k] = 1;
  DFS(k + 1);
  arr[k] = 0;
  DFS(k + 1);
}
DFS(1);
return answer;
}

console.log(solution(3));

다시 생각해보니 Solution 풀이가 공간복잡도 측면에서 훨씬 유리한 것 같다;;
내 풀이의 경우 2^n개 만큼의 배열이 선언돼야 한다;;;; 이런...