[Swift][BruteForce] 백준 1182번 (부분수열의 합)

요구능력 : 백트래킹

 

코드설명 : 

 

이 문제에서 생각해봐야할건 "어떻게해야 모든 부분수열을 구할 수 있을까?" 이다.

-7, -3, -2, 5, 8 이 있을 때

{-7}

{-7, -3}

{-7, -3, -2}

{-7, -3, -2, 5}

{-7, -3, -2, 5, 8}

{-7, -2}

...

그리고 -3부터 시작해서 위처럼 쭉 나열하고

-2부터, 5부터, 8부터...

이렇게 구하면 모든 부분수열을 구할 수 있다.

 

부분수열을 구하는건 그럼 백트래킹으로 해야겠다. 백트래킹으로 모든 경우의수를 다 검사해보는것이다.

백트래킹을 하면서 우리가 구해야하는건 부분수열의 합이다.

그래서 sum에 입력받은 연속된수열의 합을 백트래킹하면서 구했고,

그 합이 구하고자하는 값인 s와 같아졌을 때 그리고 문제에서 크기가 양수인 부분수열이랬으니 depth >=1 이면 문제에서 원하는 조건을 모두 만족하니 카운트해준다.

 

이 문제가 어렵다고 느껴지신다면 n과m시리즈를 모두 풀어보고 오시면 됩니다.

 

후기 : 논리 생각하는건 어렵진 않았는데 백트래킹을 이상하게해서 미끄러졌던문제..

let ns = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = ns[0]
let s = ns[1]

let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var visited = Array(repeating: false, count: 21)

var cnt = 0
var sum = 0
func dfs(_ depth: Int, _ start: Int){
    if sum == s && depth >= 1{
        cnt += 1
    }
    
    for i in start..<n{
        if !visited[i]{
            visited[i] = true
            sum += arr[i]
            dfs(depth + 1, i)
            visited[i] = false
            sum -= arr[i]
        }
    }
}

dfs(0, 0)
print(cnt)