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

문제 소개

주어진 배열의 부분수열중 원하는 값을 만족하는 부분수열의 갯수를 구하는 문제이다.

문제 풀이

부분수열의 합을 저장하고 합이 s와 같다면 count를 올려준다.
 
고려 사항
1. 처음에 0으로 시작하기 때문에 start라는 변수를 넣어서 dfs함수가 최소 한번은 실행되어야 current == s 조건을 확인하도록 설정했다.
2. current == s 일 경우 바로 return 했는데, 만약 부분수열중에 -1, +1 처럼 0이 되는 요소들이 뒤에 있다면 그것도 고려해야하기 때문에 return을 없애주었다.

import Foundation

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

var count = 0
var visited = Array(repeating: false, count: n)

func dfs(_ current: Int, _ idx: Int, _ start: Bool) {
    if current == s && start {
        count += 1
    }
    
    for i in idx..<n {
        if !visited[i] {
            visited[i] = true
            dfs(current+input[i], i, true)
            visited[i] = false
        }
    }
}

dfs(0, 0, false)

print(count)