[백준/BOJ] 15469번: N과 M (1)

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

15649번: N과 M (1)

문제

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

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

해설

백트래킹을 이용하여 만족하는 조건을 찾았다면 직전 단계로 돌아가 다른 경우의 수를 찾으면 된다.

소스 코드

import java.io.BufferedReader
import java.io.InputStreamReader

lateinit var visit: BooleanArray
lateinit var array: IntArray
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n, m) = br.readLine().split(" ").map{ it.toInt() }
    visit = BooleanArray(n+1)
    array = IntArray(m)
    check(0, n, m)
    br.close()
}
fun check(idx: Int, n:Int, m: Int) {
    if(idx == m) {
        for(i in array) {
            print("$i ")
        }
        return
    }
    for(i in 1 .. n) {
        if(visit[i]) continue
        visit[i] = true
        array[idx] = i
        check(idx+1, n, m)
        visit[i] = false
    }
}