PartitionEqualSubsetSum(HashMap).swift

//The first intuition is figuring out the sum we are looking for is actually sum /2 and it should be even.
//Then, the next inuition is recognizing the problem converts to finding a subset with that sum.

func canPartition(_ nums: [Int]) -> Bool {
    let total = nums.reduce(0,+)
    
    if total%2 != 0 {
        return false
    }
    
    var hashmap = [String:Bool]()
    
    return helper(nums, 0, 0, total, &hashmap)
    
    
}

func helper(_ nums: [Int], _ index: Int, _ sum: Int, _ total: Int, _ memo: inout [String:Bool]) -> Bool {
    let current = "\(index)" + "" + "\(sum)"
    
    if let val = memo[current] {
        return val
    }
    
    if sum * 2 == total {
        return true
    }
    
    if sum > total/2 || index >= nums.count {
        return false
    }
    
    
    let foundPartition = canPartition(nums, index+1, sum, total, &memo) ||
        canPartition(nums, index+1, sum+nums[index], total, &memo)
    
    memo[current] = foundPartition

    return foundPartition
    
}