15650번: N과 M (2)

문제 풀이 아이디어

모든 경우의 수를 찾을 때는 역시 재귀함수를 통해 구현하는 dfs를 사용합니다. 중복 없이 + 오름 차순의 조건에 주의해서 코드를 짭니다.

오름차순으로 출력하기 위해서는 반복문 안에서 dfs(i + 1)로 탐색하면 됩니다. 이러면 자연스럽게 중복도 없앨 수 있습니다.

다만 now가 N + 1이 될 수도 있으니 주의합시다!

코드

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

var result = [String]()

// dfs 구현
func dfs(_ now: Int) {
    // 탈출 조건
    if result.count == M {
        print(result.joined(separator: " "))
        return
    }
    
    // 오름차순으로 출력되게 now ~ N까지 반복문 설정
        //⭐️ (N + 1)로 해야지 i + 1이 N + 1일 때 에러가 발생하지 않고 반복문이 실행되지 않음
    for i in now..<(N + 1) {
        result.append(String(i))
        dfs(i + 1)
        _ = result.popLast()
    }
}

dfs(1)