class Solution:
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        count = {0: 1}
        for x in nums:
          count2 = {}
          for tmpSum in count:
            # print(x, tmpSum)
            count2[tmpSum + x] = count2.get(tmpSum + x, 0) + count[tmpSum]
            count2[tmpSum - x] = count2.get(tmpSum - x, 0) + count[tmpSum]
          count = count2
        return count.get(S, 0)

class Solution:
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()
        def dfs(target, index, path):
            if target < 0:
                return
            if target == 0:
                res.append(path)
                return
            for i in range(index, len(candidates)):
                dfs(target - candidates[i], i, path + [candidates[i]])
        dfs(target, 0, [])
        return res

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = [1]+[n for n in nums if n!=0]+[1]
        regional_max_coins = [[0 for i in range(len(nums))] for j in range(len(nums))]
        for balloons_to_burst in range(1, len(nums)-1): # number of balloons in (l,r) region
            for l in range(0, len(nums)-balloons_to_burst-1): # for m and r to be assigned legally
                r = l+balloons_to_burst+1
                for m in range(l+1,r):
                    regional_max_coins[l][r] = max(regional_max_coins[l][r], regional_max_coins[l][m]+regional_max_coins[m][r]+nums[l]*nums[m]*nums[r])
        return regional_max_coins[0][-1]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.length = 0
        
        def depth(node):
            if not node: return 0
            left = depth(node.left)
            right = depth(node.right)
            self.length = max(self.length, left + right)
            return 1 + max(left, right)
        
        depth(root)
        return self.length

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node):
            if not node: return 0, 0
            l, r = dfs(node.left), dfs(node.right)
            return max(l) + max(r), node.val + l[0] + r[0]
        return max(dfs(root))