[Swift] DFS - 합이 같은 부분집합

Swift 로 코딩테스트 문제풀기

1. 문제 설명

N개의 원소로 구성된 자연수의 집합이 주어지면, 이 집합을 두개의 부분집합으로 나누었을 때 합이 서로 같은 경우가 존재하면 "YES" 를 아니면 "NO" 를 출력하는 함수를 만들어라.

이 문제는 아마존 인터뷰 문제이다.

2. 나의 풀이

import Foundation

var ch: [Int] = []
var n: Int = 0
var ans: Int = 0
var total: Int = 0
var ret: Int = 0
func solution(_ numbers: [Int]) -> Bool {
    for i in numbers { total += i }
    func D(_ n: Int) {
        if ch.count == numbers.count {
            ans = 0
            for i in 0..<ch.count {
                ans += ch[i] == 1 ? numbers[i] : 0
            }
            ret += total/2 == ans ? 1 : 0
        } else {
            ch.append(1)
            D(n + 1)
            ch.removeLast()
            ch.append(0)
            D(n + 1)
            ch.removeLast()
        }
    }
    D(0)
    return (ret != 0)
}

3. 풀이 설명

이전 글에 올렸었던 타겟넘버 문제에서 짚고 넘어갔던 DFS 방식의 문제풀이이다.

따라서 문제풀이가 크게 다르지 않다...
똑같이 모든 가능한 합을 구해준 후 , total /2 와 같다면 true 를 때려주면 끝...

이문제는 프로그래머스에는 없는 문제이다.