멱집합

어떤 집합이 있을 때, 이 집합의 모든 부분 집합을 멱집합이라고 합니다. 멱집합을 구하는 방법에서 각 단계를 유심히 살펴보면, 순환 구조를 띠는 것을 알 수 있습니다. 여기서 순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법입니다. 따라서, 문제를 작은 단위로 줄여나가는 재귀를 응용할 수 있습니다. 예를 들어 PowerSet이라는 멱집합의 개수를 리턴하는 함수를 작성한다면, PowerSet함수에서 자기 자신을 호출하며 문제를 더 작은 문제로 문제의 크기를 줄여서 해결할 수 있습니다. 문제가 가장 작은 단위로 줄어들고, 함수가 리턴될 때 카운트를 올리는 방식으로 멱집합의 개수를 구할 수 있습니다.

집밥이 그리워
김코딩은 몇 년의 해외 출장 끝에 본가에 내려왔습니다. 오랜만에 보는 김코딩의 얼굴에 반가웠던 부모님은 상다리가 부러질 정도로 음식을 만들었습니다. 감동의 재회도 잠시, 의자에 앉아 식사를 하려던 김코딩은 무엇부터 먹어야 될지 깊은 생각에 빠졌습니다. 정성스럽게 차려 주신 만큼, 최대한 많은 방법으로 다양하게 먹고 싶었기 때문입니다.

밥은 한 가지이며 반찬은 다수일 때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.

function missHouseMeal(sideDishes) {
// TODO: 여기에 코드를 작성합니다.
// 결과를 담을 배열을 선언합니다.
let result = [];
// sideDishes를 사전식 순서로 정렬합니다.
sideDishes.sort();

// 모든 조합을 검사하는 재귀 함수를 작성합니다.
const sidePowerSet = (idx, sideDish) => {
if(idx === sideDishes.length) {
// 만약, idx와 sideDishes의 길이가 같다면(마지막까지 검토한 경우) result에 sideDish를 삽입하고 push합니다.
result.push(sideDish);
return;
}

// idx번째 요소가 포함되지 않는 경우
sidePowerSet(idx + 1, sideDish);

// idx번째 요소가 포함되는 경우
sidePowerSet(idx + 1, [ ...sideDish, sideDishes[idx] ]);

};

// 0번째 인덱스와 빈 배열을 인자로 받는 재귀 함수를 실행합니다.
sidePowerSet(0, []);

// 결과를 사전식 순서로 정렬합니다.
return result.sort();
}