문제

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

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

입력
인자 1: sideDishes
String 타입의 영문으로 된 반찬이 나열되어 있는 배열
출력
Array 타입을 리턴해야 합니다.
밥과 함께 먹을 수 있는 반찬의 모든 경우의 수가 담긴 배열
주의사항
반찬은 영문으로 작성이 되어 있습니다.
반찬은 중복되지 않습니다.
반찬을 먹지 않는 것도 포함됩니다. (출력되는 2차원 배열은 빈 배열을 포함합니다.)
반찬은 3개 이상 99개 이하입니다.
출력되는 배열은 전부 사전식 순서(lexical order)로 정렬되어야 합니다.
ex)
입출력 예시
let output = missHouseMeal(["eggroll", "kimchi", "fishSoup"]);
console.log(output);

[ [], 
  [ 'eggroll' ], 
  [ 'eggroll', 'fishSoup' ], 
  [ 'eggroll', 'fishSoup', 'kimchi' ], 
  [ 'eggroll', 'kimchi' ], 
  [ 'fishSoup' ], 
  [ 'fishSoup', 'kimchi' ], 
  [ 'kimchi' ]
] 

멱집합

멱집합: 어떤 집합이 있을 때, 이 집합의 모든 부분집합을 멱집합
부분집합을 나열하는 방법에서 가장 앞 원소(혹은 임의의 집합 원소)가 있는지, 없는지에 따라 단계를 나누는 기준을 결정
=> 재귀적이다

레퍼런스

function missHouseMeal(sideDishes) {

  // 결과를 담을 배열을 선언합니다.
  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가 같을 때까지 ++해서 result에 []push를 하고 return을 해야 아래 코드로 넘어간다 
    
   마지막과 같을 때 push [], return 
   //result = [[]]
   

    // idx번째 요소가 포함되는 경우
    sidePowerSet(idx + 1, [...sideDish, sideDishes[idx]]);
    //1,[0번째부터 뒤에서 넣는다]
    //길이가 같지 않으면 안 넣는다 
    //2, [0번째, 1번째] 
    //이제 같으니까 넣는다 
    //[[],[0번째, 1번째]] 리턴?? 한개짜리는 어디서 합한거지
    
  };

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

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

레퍼런스 이해하는 것도 굉장히 어려운 문제였다.
출력 예시를 보면
1)kimchi의 멱집합을 구하고: [], [kimchi]
2)kimchi의 모든 멱집합 앞에 fishsoup을 추가: [fishsoup], [fishsoup, kimchi]
3)여기에 또 eggroll을 모든 배열의 첫 요소로 추가:
[eggroll, fishsoup], [eggroll, fishsoup, kimchi]
식으로 하나씩 추가해나가면 된다

각 배열마다 사전식 순서로 요소들을 넣기 위해서 뒤에서부터 추가하는 것이다

즉 마지막 요소부터 멱집합을 구해서 이전 요소들을 하나씩 추가하는 형식이므로
result에 배열을 넣을 때는 sideDishes의 마지막 요소일때로 하면 된다

사실 top level에서 return을 언제 하는지 좀 가늠이 안간다
idx=0이고 top level에서 ++을 하지 않으니까

if문 아래 재귀함수 두개를 리턴하고 끝나는데 그러면 함수 실행이 끝난건가?
아무튼 재귀함수 두개 리턴이 끝나면 result에 원하는 값이 다 들어오기는 한다
마지막에 result.sort()를 통해 사전식 순서대로 정렬을 할 수 있다.