15655번: N과 M (6)

문제 풀이 아이디어

고른 수열이 오름차순이어야 하므로 입력 받은 배열을 정렬합니다. 그리고 반복문 안에서 dfs에 넘길 때 dfs(i + 1)로 해주어야 중복 없이 오름차순의 수열을 만들 수 있습니다.

코드

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]

// 입력 배열 with 정렬
let array = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()

// 결과 및 방문 배열
var result = [Int]()

// dfs 구현
func dfs(_ now: Int) {
    // 탈출 조건
    if result.count == M {
        print(result.map { String($0) }.joined(separator: " "))
        return
    }

    // 오름차순이어야 하므로 now부터 순환
    for i in now..<N {
        result.append(array[i])
        dfs(i + 1)
        _ = result.removeLast()
    }
}

dfs(0)