Go DFS solution (33ms)


  • 0
    S
    func findTargetSumWays(nums []int, S int) int {
        // sums[i] stores the sum of subarray nums[i:]
        sums := make([]int, len(nums))
        sums[len(nums)-1] = nums[len(nums)-1]
        for i:=len(nums)-2; i>-1; i-- {
            sums[i] = sums[i+1] + nums[i]
        }
        
        res := 0
        findHelper(nums, 0, 0, S, &res, sums)
        return res
    }
    
    func findHelper(nums []int, index int, curSum int, S int, res *int, sums []int){
        if index == len(nums){
            if curSum == S{
                *(res) = *(res) + 1
            }
            return
        }
        // optimization: if sum of positive nums left(sums[index]) is less than the sum still needed(S-curSum), then return
        if S - curSum > sums[index] {
            return
        }
        
        findHelper(nums, index+1, curSum+nums[index], S, res, sums)
        findHelper(nums, index+1, curSum-nums[index], S, res, sums)
    }
    

Log in to reply
 

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