# Swift solution - DFS, Divide and Conquer

• ``````class Solution {
func findTargetSumWays_DFS(_ nums: [Int], _ S: Int) -> Int {
if nums.count == 0 {
return 0
}

let n = nums.count
var result = 0
var sums = [Int](repeatElement(0, count: n))

sums[n - 1] = nums[n - 1]
for i in stride(from: n - 2, through: 0, by: -1) {
sums[i] = sums[i + 1] + nums[i]
}

DFS(nums, sums, S, 0, &result)

return result
}

private func DFS(_ nums: [Int], _ sums: [Int], _ target: Int, _ pos: Int, _ result: inout Int) {
if pos == nums.count {
if target == 0 {
result += 1
}
return
}

if sums[pos] < abs(target) {
return
}

DFS(nums, sums, target + nums[pos], pos + 1, &result)
DFS(nums, sums, target - nums[pos], pos + 1, &result)
}

func findTargetSumWays_DividAndConquer(_ nums: [Int], _ S: Int) -> Int {
if nums.count == 0 {
return 0
}

var cache = [String: Int]()

return helper(nums, 0, 0, S, &cache)
}

private func helper(_ nums: [Int], _ pos: Int, _ sum: Int, _ target: Int, _ cache: inout [String: Int]) -> Int {
let key = "\(pos)->\(sum)"
if cache.keys.contains(key) {
return cache[key]!
}

if pos == nums.count {
if sum == target {
return 1
} else {
return 0
}
}

let add = helper(nums, pos + 1, sum - nums[pos], target, &cache)
let minus = helper(nums, pos + 1, sum + nums[pos], target, &cache)
let result = add + minus

cache[key] = result

return result
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.