백준 15649 N과 M(1)

[공부정리] 순열 vs 조합 vs 중복순열 vs 중복조합 (feat. 백준 N과 M 문제 시리즈)

---

문제

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

15649번: N과 M (1)

접근

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

➡️ 수의 범위가 작아 완전탐색 으로 접근

 

중복 없는 수열

➡️ 백트래킹

➡️ 수열 문제니까 조합(combination) 또는 순열(permutation) 인데, 중복이 없다고 했으므로 순열 문제.

풀이

const input = require("fs").readFileSync('/dev/stdin').toString().trim().split(" ").map(Number);

const [n, m] = input;
let result = "";
const output = [];
const checked = Array(n).fill(false);

function dfs(cnt) {
	
    if (cnt === m) {
        result += `${output.join(" ")}\n`;
        return;
    }

    for (let i = 0; i < n; i++) {
        if (checked[i] === true) continue;
        checked[i] = true;
        output.push(i + 1);
        dfs(cnt + 1);
        output.pop();
        checked[i] = false;
    }
}

dfs(0);

console.log(result);