虎牙9.23笔试题解---第三题：三国杀

题目大意是说：
有一个差不多长度为4~9的数组，
由扑克牌的值构成，包括JQK，分别代表11,12,13，其他都是数字

然后呢，你需要找一个子数组，使得其能够刚好分成两个，总和大小相等的2份，求最长的这样的子数组长度是？

思路是一个热心网友提供的，用combinations+我自己以前的做过的一个题目《和为k的子数组》，也就是dfs来做

步骤：首先用combinations把所有可能的组合都找到（毕竟数组长度小），长度从1到n都要有，可以先筛掉一些肯定不符合条件的，比如不能被2整除，长度不足2的。然后呢，用dfs去判断这个数组是否能被平分为2。

代码如下：

from itertools import combinations
arr = ['1','2','7','Q']
res = 0
def f(arr):
    dic = {
        'J':11,
        'Q':12,
        'K':13
    }
    n = len(arr)
    
    for i in range(n):
        if arr[i] in dic:arr[i] = dic[arr[i]]        
    nums = [int(x) for x in arr]
    lists = []
    for i in range(n+1):
        combs = combinations(nums,i)
        for x in combs:
            if len(x)>1 and sum(x)%2==0:lists.append(x)
            
    def dfs(s,cur_sum,cur_use,target):
        global res
        if cur_sum>target:return
        if cur_sum==target:
            res = max(res,len(s))
            return
        for i,x in enumerate(s):
            if (2<<i)&cur_use==0:dfs(s,cur_sum+x,cur_use|(2<<i),target)
             
    for s in lists:
        dfs(s,0,0,sum(s)//2)
    return res

f(arr)