15665번: N과 M (11)

문제 풀이 아이디어

중복을 허용하므로 중복체크 배열 없이 dfs를 수행하면 됩니다. 다만 수열 자체의 중복은 체크해주어야 합니다.

코드

// 입력 받기
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() {
    if result.count == M {
        let resultString = result.joined(separator: " ")
        if !check.contains(resultString) {
            check.insert(resultString)
            print(resultString)
        }
        return //👉 if절이 실행되지 않더라도 return 되어야 함!
    }
    
    for i in 0..<N {
        result.append(String(array[i]))
        dfs()
        _ = result.popLast()
    }
}

dfs()