문제

https://www.acmicpc.net/problem/15649

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

풀이방법

처음 생각한 풀이대로 코드를 작성하니 풀리는 간단한 문제였다.

0. 재귀함수 sol 호출([])
1. for문 i~N까지
2. 만약 arr안에 i가 없다면 arr에 i를 더해줌 -> if (!arr.includes(i))
3. i를 더한 arr을 재귀함수 sol의 매개변수로 넘겨줌 -> sol(...arr, i)
4. arr의 길이가 M과 같다면 재귀함수를 종료함 -> if (arr.length === M)

//init용
const stdin: string[] = (process.platform ==='linux'
? require('fs').readFileSync(0, 'utf-8')
: `
4 4
`).trim().split('\n');

const input = (()=>{
    let line = 0;
    return ()=> stdin[line++].split(" ").map( v => +v);
})();

const [N, M] = input();
const result: number[][] = [];

const sol = (arr: number[]) => {
    if (arr.length === M){
        result.push(arr);
        return;
    }
        
    for (let i=1; i<=N; i++) {
        // arr안에 i값이 없어야 다음 재귀로 진입
        if ( !arr.includes(i)) {
            sol([...arr, i]);
        }
    }
}

sol([]);
result.map( v=> console.log(v.join(" ")));