#可以把切割的过程看成二叉树分裂的过程，每种切割法对应一颗二叉树，二叉树的所有内部结点和
#为总开销。只要构造出所有的二叉树，就能找到最小开销。给定的例子测试可行。
#复杂度感觉有点高，具体多少我也分析不来。。。
class TreeNode():
    def __init__(self,val):
        self.val=val
        self.left=None
        self.right=None
class Solution():
    def leastPay(self,length,array):
        trees=self.toTrees(array)
        least=length*(length-1)/2
        for tree in trees:
            least=min(self.toPay(tree),least)
        return least
    #构造所有可能的二叉树
    def toTrees(self,array):
        if len(array)==1:
            return [TreeNode(array[0])]
        trees=[]
        leftEs,rightEs=self.divideElements(array)
        for leftE,rightE in zip(leftEs,rightEs):
            for leftT in self.toTrees(leftE):
                for rightT in self.toTrees(rightE):
                    root=TreeNode(sum(array))
                    root.left=leftT
                    root.right=rightT
                    trees+=[root]
        return trees
    #把当前剩余元素随机划分到左右两颗子树，返回所有可能的划分情况
    def divideElements(self,array):
        if len(array)==2:
            leftEs=[[array[0]],[array[1]]]
            rightEs=[[array[1]],[array[0]]]
            return (leftEs,rightEs)
        leftEs=[]
        rightEs=[]
        for i in range(len(array)):
            tempLs,tempRs=self.divideElements(array[:i]+array[(i+1):])
            for j in range(len(tempLs)):
                leftEs+=[tempLs[j]+[array[i]]]
                rightEs+=[tempRs[j]]
                leftEs+=[tempLs[j]]
                rightEs+=[tempRs[j]+[array[i]]]
        return (leftEs,rightEs)
    #计算每棵树对应的开销
    def toPay(self,tree):
        if not tree.left and not tree.right:
            return 0
        elif tree.left and tree.right:
            return tree.val+self.toPay(tree.left)+self.toPay(tree.right)
        else:
            return "ERROR"