[백준] (Swift) 15657번 - N과 M(8) (feat. 드디어마지막... DFS, 백트래킹)

🟠 문제

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

15657번: N과 M (8)

 

🟠 나의 풀이

중복을 허용해줘야하기 때문에 if !stack.contains 부분을 빼서 방문확인을 안해주었고, 해당 수보다는 작거나 큰 수가 옆에 올 수 있기 때문에 매개변수로 현재 방문하고 있는 i 값을 넘겨주었다. 

똑같은 문제는 N과 M(4)번!

https://didu-story.tistory.com/375

[백준] (Swift) 15651번 - N과 M(4) (feat. DFS, 백트래킹)

 

🟠 정답코드

let nm = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nm[0]
let m = nm[1]
let arr = readLine()!.split(separator: " ").map{ Int($0)! }.sorted(by: <)

var stack = [String]()
var answer = ""

private func dfs(start: Int) {
    if stack.count == m {
        answer += stack.joined(separator: " ") + "\n"
        return
    }

    for i in start..<n {
        stack.append(String(arr[i]))
        dfs(start: i)
        stack.removeLast()
    }
}

dfs(start: 0)
print(answer)