记网易面试题《一》

任意一个不为空的数组 分给两个子数组 要求 两个数组都为True

————————————————————————————————————————————————————

1. 为降低难度，还特意不考虑重复元素
2. 为降低难度，还特意没有指定两位以上的元素 【1,2,3,4,5】

 ##枚举真的是个铁憨憨 用递归的写法 并进行剪枝（优化）
def divide(a,length,target,tmp,new):

    """
    :param a: 代表列表的字符串形式 
    :param length: 代表字符串长度 
    :param target: 临时变量 用来记录第一个数组分到的元素内容
    :param tmp: 代表第一个数组里面分得的元素数量
    :param new: 递推的记录量 下一次取得位置  比如 对于 1 2 3 4 5 6   当第一数组的长度为2 且第一次取得的是1 第二次取 2  1 ，2
                                                                                      第三次取 3  1,  3
    :return: 
    """
    if len(target) == tmp:
        print(target,''.join(set(a)-set(target)))
        return
    for i in range(tmp,length+1):
        # 被分到第一个数组里面的元素 数量i
        #避免重复取 Cn m的取法 和 Cn m-n的取法是一样的  说明可以优化一半
        if length - i < i :
            break
        for j in range(new,length):
            # 当长度为偶数的时候 还是会有大量重复 进一步优化 因为去123 就不必再去取456 了
            if length - i == i and target and target[0] != a[0]:
                return
            if j+1 <= length:
                divide(a,length,target+a[j],i,j+1)
        # 跳出当前的递归栈 比如第一个数组元素长度为2 时 对于第一个元素 取 1,2 1,3, 1,4 1,5 取完之后 我们需要从2开始取
        #但是在当前的循环里面 它会去判断数组长度为3的情况 （我们为2的情况都没有判断） 如果不进行着一步剪枝 会造成大量的重复
        if tmp > 1:
            break

上述代码 值适合没有重复的元素 被分组列表元素 全部是单值的情况 除了提供思路一点用都没有

——————————————————————————————————————————————————————————————————————————————————————————————————————————————————

考虑 元素可以不为单值的情况.....使用列表
难点在于 列表不像字符串那样可以很容易恢复状态 （函数里面传参是不能 list.append(ele)）这样是一个空值

def divide(a,length,target,tmp,new):

    if target and len(target) == tmp:
        print('tar', target)
        target.pop()
        return
    for i in range(tmp,length+1):

        if length - i < i:
            break
        for j in range(new, length):

            if length - i == i and target and target[0] != a[0]:
                return
            if j+1 <= length:
                # 因为target.append(a[j]) 是一种无效的传参 所以直接传参 会导致传递none值
                target.append(a[j])
                divide(a, length, target, i, j+1)

        if tmp > 1:
            # 恢复状态
            target.pop()
            break

代码要求完成的时间是15min 显然失败了---------------------

1. 确定思路：按照第一个列表里面被分得的元素数量去讨论
2. 第一次进行重复判断
3. 对需要的元素进行状态取值
4. 确定递归需要的参数 和 终止条件
5. 继续 优化 长度偶数时的重复判断 和 不必要的递归