[DFS] 수열 추측하기

문제정의

0. 두 개의 정수 N과 F를 입력받는다
1. 가장 첫번째 줄은 1부터 N까지 숫자가 랜덤하게 들어간다
2. 이후부터는 왼쪽오른쪽 더한 값으로 계속 적어낸다
3. 마지막의 수는 F로 끝난다
4. 랜덤하게 나열되는 첫번째 수들을 프린트하기

(Tip) 순열은 n! 가짓수를 다 들여다보는 방법밖에 없다
n!를 다들여다보지 않는 방법을 찾아보자

풀이

import Foundation

let n1 = 4
let n2 = 16
var arr1 = [Int](repeating: 0, count: n1)
var arr2 = [Int](repeating: 1, count: n1)
var arr3 = [Int](repeating: 0, count: n1+1)
var solArr: [Int] = []

func DFS(_ h: Int, _ sum: Int) {
    
    if h == n1 && sum == n2 {
        for j in arr1 {
           print(j, terminator: " ")
        }
        exit(0)
    } else {
        for i in 1...n1 {
            if arr3[i] == 0 {
                arr3[i] = 1
                arr1[h] = i
                DFS(h+1, sum+(arr1[h]*arr2[h]))
                arr3[i] = 0
            }
        }
    }
}


func sol() {
    for i in 1..<arr2.count {
        arr2[i] = arr2[i-1]*(n1-i)/i
    }
    DFS(0,0)
}
sol()