15666번: N과 M (12)

문제 풀이 아이디어

사용한 수를 또 사용해도 되므로 중복 체크를 사용할 필요가 없습니다. 입력 array를 정렬하고 index ~ N을 완전탐색하면 자연스럽게 비오름차순을 구현할 수 있습니다.

코드

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

// 결과 저장 배열
var result = [String]()

// 중복 체크 Set
var check = Set<String>()

func dfs(_ index: Int) {
    if result.count == M {
        let resultString = result.joined(separator: " ")
        if !check.contains(resultString) {
            check.insert(resultString)
            print(resultString)
        }
        return //👉 if절이 실행되지 않더라도 return 되어야 함!
    }

    for i in index..<N {
        result.append(String(array[i]))
        dfs(i)
        _ = result.popLast()
    }
}

dfs(0)