BOJ: #1182 - 부분수열의 합

나는 어떤 유형의 정형화된 코드를 외우면, 대부분의 문제를 그 방식을 응용해서 푼다. 그래서 이 문제도 다음과 같은 비효율적인 코드가 나왔다. 시간을 보니 다른 분에 비해 약 50배가 느렸다(…). 그래서 더 간결한 코드가 궁금해서 살펴보았는데, 굳이 배열을 쓰지 않고, 변수에 저장해서 재귀를 넘기고(?), 하는 방식으로 하더라. 아무튼 이건 나중에 다시 풀어봐야겠다.

문제

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

내가 작성한 코드

Swift

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0]
let target = input[1]
let nums = readLine()!.split(separator: " ").map { Int(String($0))! }
var count = 0
 
var picked = [Int]()
var visited = Array(repeating: false, count: n)
func pick(toPick: Int, start: Int) {
    if toPick == 0 {
        if picked.reduce(0, +) == target {
            count += 1
        }
        return
    }
    for i in start..<n {
        if visited[i] {
            continue
        }
        visited[i] = true
        picked.append(nums[i])
        pick(toPick: toPick - 1, start: i + 1)
        picked.removeLast()
        visited[i] = false
    }
}
 
for i in 1...n {
    pick(toPick: i, start: 0)
    visited = Array(repeating: false, count: n)
}
 
print(count)