해당 포스팅은 프로그래머스의 메뉴 리뉴얼 풀이 다룬다. 문제 링크
코드는 javascript로 작성하였으며 백트래킹으로 풀이하였다.

풀이

• input으로 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어진다.

• 각 세트 메뉴 개수에 대해 손님들이 주문한 단품메뉴의 조합을 구한다. 예시로 손님이 주문한 단품메뉴들이 "ABCDE"이고 단품메뉴 갯수가 2면, 메뉴들 중 2개를 골라 조합을 구하면 된다(5C2).

• 백트래킹을 이용해 손님들이 주문한 메뉴의 조합을 구한다. 조합은 해시에 저장해둔다. 백트래킹으로 조합 구하는 방법은 해당 포스팅에 정리되어 있다.

• 각 세트 메뉴 개수에 대해 손님들이 주문한 메뉴의 조합들 중 가장 개수가 많았던 세트(maxSet)를 answer에 넣는다. 이 때 maxSet이 여러 개라면 전부 넣어준다.

전체 코드

function solution(orders, courses) {
    const answer = [];
    // 각 세트 메뉴 개수에 대해 손님들이 주문한 단품메뉴의 조합을 구한다. 
  	// 예시로 손님이 주문한 단품메뉴들이 "ABCDE"이고 단품메뉴 갯수가 2면, 
  	// 메뉴들 중 2개를 골라 조합을 구하면 된다(5C2).
    for (let course of courses) {
        const oH = new Map();
        for (let order of orders) {
          	// 백트래킹을 이용해 손님들이 주문한 메뉴의 조합을 구한다.
          	// 조합은 해시에 저장해둔다.
            backTracking(course, oH, order, 0, '', 0);
        }
      	// 각 세트 메뉴 개수에 대해 손님들이 주문한 메뉴의 조합들 중 가장 개수가 많았던 세트(maxSet)를 answer에 넣는다. 
      	// 이 때 maxSet이 여러 개라면 전부 넣어준다.
        getMaxSet(oH, answer);
    }
    
    return answer.sort();
}

// 각 세트 메뉴 개수에 대해 손님들이 주문한 메뉴의 조합들 중 가장 개수가 많았던 세트(maxSet)를 answer에 넣는다.
function getMaxSet(map, answer) {
    // 가장 개수가 많았던 세트의 크기를 구하기
  	let maxMapSize = 0;
    for (let v of map.values()) {
        if (maxMapSize < v) {
            maxMapSize = v;
        }
    }
    // maxSet를 해시에 넣어주기
    for (let [k, v] of map) {
        if (maxMapSize <= 1) continue;
        if (maxMapSize === v) {
            answer.push(k);
        }
    }
}

// 백트래킹을 이용해 손님들이 주문한 메뉴의 조합을 구한다.
// 조합은 해시에 저장해둔다.
function backTracking(end, map, order, idx, str, start) {
    if (idx === end) {
        const comb = str.split('').sort().join('');
        if (map.has(comb)) {
            map.set(comb, map.get(comb)+1);
        }
        else {
            map.set(comb, 1);
        }
        return;
    }
    
    for (let i=start; i<order.length; i++) {
        const ch = order.charAt(i);
        backTracking(end, map, order, idx+1, str+ch, i+1);
    }
}