[node.js] 로또 ( 백준 6603번 )

// 백준 6603번 로또를 풀었습니다.

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const combinations = function* (elements, selectNumber) {
    for (let i = 0; i < elements.length; i++) {
        if (selectNumber === 1) {
            yield [elements[i]];
        } else {
            const fixed = elements[i];
            const rest = combinations(elements.slice(i + 1), selectNumber - 1);

            for (const a of rest) {
                yield [fixed, ...a];
            }
        }
    }
};

const input = [];

rl.on("line", (line) => {
    input.push(line);
}).on("close", () => {
    const lottoes = input
        .slice(0, -1)
        .map((el) => el.split(" ").slice(1).map(Number));

    const answer = lottoes.map((lotto) => {
        const res = [];
        for (const a of combinations(lotto, 6)) {
            res.push(a);
        }
        res.push([]);
        return res;
    });

    answer
        .flat(1)
        .slice(0, -1)
        .forEach((el) => console.log(el.join(" ")));
});

조합을 재귀를 이용해서 구현하였다.
아래의 흐름을 따라 가보자.

• 현재 골라야 하는 개수가 1개라면, 각 요소를 순회하면서 1개씩 돌려주면 된다.
• 골라야 하는 개수가 1개 이상이라면,
  • 전체 요소 중 1개를 고른다.
  • 그 요소의 다음 요소들을 모은 집합에서 개수를 1개만큼 줄인 조합을 다시 구한다.
  • 이 둘을 합쳐서 돌려준다.

이렇게만 하면 모든 조합을 구할 수 있다.
로또라고 해서 순간 순열인 줄 알았는데, 생각해보니 조합이었다. 조합도 순열과 크게 로직이 다르진 않다.
특이할 사항으로는, 순열은 언제나 전체 요소를 순회하지만, 조합은 fixed된 것으로부터 다음 요소들만 보면 된다는 점이다.
이는 조합이 중복을 허용하지 않기에 그러하다.

여담

여담인데, C++로 할 당시에는 45개 중에 6개를 방문하는 DFS로 해석하여 풀었었다.