"""
Problem 68: https://projecteuler.net/problem=68


"""


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/22
'''


def combins(nums:list,C:int) -> list:
    '''
    for [1,2,3,...,n], outer numbers [ai] and inter numbers [bi] have same size ,
    so n must be even, n =2k.

    sum(ai) + sum(bi) = sum(1,2,3...2k), i=1,2,3,...k
    sum(ai) + 2*sum(bi) = k*C, C is sum of any line
    ==> sum(bi) = k*C - k(2k+1)
    due to sum(1,2,3,...,k) <= sum(bi) <= sum(k+1,k+2,k+3,...,2k),
    we can get that:

                (5k+3)/2 <= C <= (7k+3)/2
    e.g. 
    (1) n=6(k=3),
                C = 9,10,11,12
    (2) n=10(k=5),
                C = 14,15,16,17,18,19
    
    Of course, every Ci just be potential solution before verification. 

    ai + bi + b_i+1 = C,
    so, min(C)-n <= bi + b_i+1 <= max(C)-1
    '''
    
    results = []
    
    def backtrack(path, ns, start):
        nonlocal results
        
        lens = len(ns)
        k = lens//2
        
        if len(path) == k:
            combin = path + [None]*k
            
            for i in range(k-1):
                combin[k+i] = C - path[i] - path[i+1]
            combin[-1] = C - path[0] - path[-1]
            
            # combin = [bi] + [ai]
            if sorted(combin) == list(ns):
                res = [(combin[k+i],combin[i],combin[i+1]) for i in range(k-1)]
                res.append((combin[lens-1],combin[k-1],combin[0]))
                # res = [(a1,b1,b2),(a2,b2,b3),...,(ak,bk,b1)]                 
                results.append(res)
                # print(f'bi = {path} is ok!')
                return
            else:
                # print('fail')
                return
        
        for i in range(start,lens):
            if ns[i] in path:
                continue
            if path:
                if not C-ns[-1] <= path[-1]+ns[i] <= C-ns[0]:
                    continue
                
            path.append(ns[i])
                
            backtrack(path,ns,0)
            
            path.pop()
    
    backtrack([],nums,0)  # root
    return results 
            
            


def solution() -> list:
    '''
    10 must be in outer [ai], else getting 17-digits.
    
    for gettiing max number, we wish that the first digit is 9(not 10)
    '''
    
    nums = [1,2,3,4,5,6,7,8,9,10]
    
    # (5k+3)/2 <= C <= (7k+3)/2
    ci = [14,15,16,17,18,19]
    res = []
    for c in ci:
        res += combins(nums,c)
    
    maxres = [(0,0,0)]
    for combin in res:
        bi = [combin[i][1] for i in range(5)]
        if 10 in bi:
            continue
        if combin[0][0] == 10:
            continue
            
        maxres = combin if combin > maxres else maxres
    
    return maxres
    
    
if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)
    
    print(solution())
    # [(9, 4, 1), (10, 1, 3), (6, 3, 5), (7, 5, 2), (8, 2, 4)]
    
    print(combins([1,2,3,4,5,6,7,8,9,10],15))
    # ci = 15,18, no solution