알고리즘

[Swift] 백준 - 부분 수열의 합

고고 2022. 2. 3. 11:53

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

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

 

 

조합으로 풀었습니다

import Foundation

let arr = readLine()!.split(separator: " ").map { Int($0)! }
let N = arr[0]
let S = arr[1]

let array = readLine()!.split(separator: " ").map { Int($0)! }

var count = 0

func combi(_ nums: [Int], _ targetNum: Int) {
    func combination(_ index: Int, _ nowCombi: [Int]) {
        if nowCombi.count == targetNum {
            if nowCombi.reduce(0, +) == S {
                count += 1
            }
            return
        }
        for i in index..<nums.count {
            combination(i + 1, nowCombi + [nums[i]])
        }
    }
    
    combination(0, [])
}

for i in 1...N {
    combi(array, i)
}

print(count)
저작자표시 비영리 변경금지 (새창열림)