PartitionEqualSubsetSum(Recursion).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
    }
    
    return canPartition(nums, 0, 0, total)
    
    
}

func canPartition(_ nums: [Int], _ index: Int, _ sum: Int, _ total: Int) -> Bool {
    if sum * 2 == total {
        return true
    }
    
    if sum > total/2 || index >= nums.count {
        return false
    }
    
    return canPartition(nums, index+1, sum, total) ||
           canPartition(nums, index+1, sum+nums[index], total)
}