• 문자열을 입력 받아서 각 문자를 가지고 만들 수 있는 모든 부분집합을 구한다. (배열)

function powerSet(str) {
	// str문자열을 배열로 바꿔주고 소팅한다.
	let arr = str.split('').sort();
	// 최종 리턴할 배열 변수를 만들어준다.
	let result = [''];

	let subset = (result, target) => {
		// result배열을 복사한다.
		// result.slice()를 사용해도 무방하다.
		let copy = [...result];
		
		// copy를 탐색한다.
		for(let i=0; i<copy.length; i++) {
			// copy[i]번째에 target 문자열을 합쳐준다.
			copy[i] = copy[i] + target;
			// 합쳐진 문자열을 result에 push해준다.
			result.push(copy[i]);
		}
		return result;
	}

	// arr을 탐색한다.
	for(let i=0; i<arr.length; i++) {
		// 중복값이 result에 있으면 안되니까 중복이 없는 경우만 for문을 돌게한다.
		if(!result.includes(arr[i]) {
			subset(result, arr[i]);
		}
	}
	// 최종적으로 result를 소팅해서 리턴한다.
	return result.sort();
}

• 멱집합 : 어떤 집합의 모든 부분집합의 집합(중복없음)
  • 원소의 개수가 n개인 모든 가능한 부분집합의 개수는 2^n개이다.
  • ['a', 'b', 'c']라고 가정하면 부분집합을 구하는 경우는 a를 포함하는 경우, a를 포함하지 않는 경우로 나눌 수 있다.
    • a를 포함하지 않는 경우 : ['b', 'c']의 부분집합을 나열
    • a를 포함하는 경우 : ['b', 'c']의 부분집합에 'a'를 추가한 부분집합을 나열
    • 두가지 경우를 합치면 2^n개가 된다.
  • 가장 일반적인 방법 : 재귀함수
    • 탈출 조건 : 배열의 인덱스가 가장 마지막에 도달했을 경우(배열과 길이가 같을 때) 부분집합을 구한 뒤 탈출시킨다.
    • 이진 탐색 트리 처럼 왼쪽의 경우는 포함하는 경우로 true, 오른쪽의 경우 포함하지 않는 경우로 false로 설정해도 된다.

const getSubsets = function (arr) {
	// ['a', 'b', 'c']라고 가정하면 [false, false, false]
  let flag = new Array(arr.length).fill(false);
  const subSets = [];

	// 부분 집합 구하는 재귀 함수, DFS 알고리즘
  const subSet = (depth) => {
		// 트리의 끝에 다다른 것 ==> 재귀 종료 조건
    if (depth === arr.length) { 
			// 해당 flag true => 부분집합 포함
			// flag에 true인 index와 같은 index에 있는 arr만 filter해서 넣어준다.
      subSets.push(arr.filter((value, index) => flag[index])); 

			return;
    } else {
				flag[depth] = true;  // 해당 depth의 flag true = 트리의 왼쪽
		    subSet(depth + 1);   // 트리의 왼쪽에 대해 재귀호출

		    flag[depth] = false; // 해당 depth의 flag false = 트리의 오른쪽
		    subSet(depth + 1);   // 트리의 오른쪽에 대해 재귀 호출
			}    
  }; 
  subSet(0); // depth 0 부터 시작
  return subSets;
}