1. N과 M (6)

유망할 때 - 중복되는 수열을 여러 번 출력하면 안되는것이 조건 (중복된 N개의 값이 없음)

현재 진행하는 배열이 스택에 들어있는 값과 동일한게 있다면 그건 유망하지 않으므로 가지치기

유망하다면, 스택에 요소를 넣고, 다음 요소를 선택하기 위해 호출한다.

호출된 재귀가 끝났다면 스택에서 제거함으로써 다시 접근 가능하게끔 함

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 = [Int]()// 선택된 요소를 저장하는 스택
var answer = ""

private func dfs(start: Int) {
// 스택의 크기가 m이면, m개의 요소를 모두 선택한 것이므로 결과를 저장
    if stack.count == m {
        answer += stack.map{ String($0) }.joined(separator: " ")
        answer += "\\n"
        return
    }

// start부터 n까지 인덱스를 가진 요소에 대해 탐색
    for i in start..<n {
// 이미 스택에 들어있는 요소는 건너뜀.
        if !stack.contains(arr[i]) {
            stack.append(arr[i])// 스택에 요소를 추가
            dfs(start: i+1)// 다음 요소를 선택하기 위해 재귀 호출
            stack.removeLast()// 백트래킹. 스택에서 마지막 요소를 제거
        }
    }
}

dfs(start: 0)
print(answer)

1. N과 M 9

유망할때 - 중복되는 수열을 여러 번 출력하면 안됨 (근데 여기는 중복된 N개의 값이 있음)

이 사람의 코드는 사실 아래는 모든 요소를 탐색하는건데 끝날때 조건에 작성한 코드가 좀 다름

result 배열의 개수가 M개가 됐을 때, 중복없는 결과를 뽑기위해 집합을 사용했음

집합에 이번에 들어온 값이 존재하지 않다면, 집합에 값을 넣어주고, 해당 값은 출력함

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

// 방문 여부를 기록하는 배열
var visited = Array(repeating: false, count: N)
// 선택된 요소를 저장하는 배열
var result = [String]()
// 이미 출력한 수열을 기록하는 집합
var check = Set<String>()

func dfs() {
    // M개의 요소를 모두 선택했으면 출력
    if result.count == M {
        let resultString = result.joined(separator: " ")
        // 중복되는 수열을 제거하기 위해 집합에 포함되어 있지 않은 경우에만 출력
        if !check.contains(resultString) {
            check.insert(resultString)
            print(resultString)
        }
        return
    }

    // 모든 요소 탐색
    for i in 0..<N {
        if !visited[i] {
            visited[i] = true
            result.append(String(array[i])) 
            dfs()
            visited[i] = false 
            _ = result.popLast()  // 백트래킹, 마지막에 추가한 요소를 제거
        }
    }
}

dfs()

1. BOJ_10819_차이를 최대로

사실 가지치기하는 조건이 없어서 브루트포스나 백트래킹이나 똑같음