Swift solution - DFS, Divide and Conquer


  • 0
    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
        }
    }
    

Log in to reply
 

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