문제

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

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

문제풀이

처음 N과M(1)문제에서 고른 수열은 오름차순이어야 한다는 조건이 더 생겼다.
그래서 재귀함수에 진입하는 조건을 아래와같이 수정해 주었다.

/* 이전 조건문 */
if ( !arr.includes(i)) { ... }
/* 수정한 조건문 */
if ( arr[arr.length-1] < i || arr.length === 0) { ... }

arr 배열의 마지막이 i보다 작다면 오름차순 정렬이 되기때문에 정답이 나온다
arr.length === 0이라는 조건을 추가해준 이유는 처음에 배열에 아무것도 없으면
정상적으로 작동하지 않기 때문이다.

/* 전체코드 */
//init용
const stdin: string[] = (process.platform ==='linux'
? require('fs').readFileSync(0, 'utf-8')
: `
4 2
`).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보다 작거나 arr이 비었으면 재귀 진입
        if ( arr[arr.length-1] < i || arr.length === 0) {
            sol([...arr, i]);
        }
    }
}

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