给定数组求任意个数元素和小于且最接近一个数_没事就写写代码的博客

last = []
left = []

def sort_dict(last):         #返回字典最小value对应的item
    res = dict()
    values = list(last.values())
    keys = list(last.keys())
    min = [0]
    for index in range(len(values)):
        if values[index] < values[min[0]]:
            min.clear()
            min.append(index)
        elif values[index] == values[min[0]]:
            min.append(index)
    for index in min:
        key = keys[index]
        res[key] = last[key]
    return res

def max_num(a, n):  # 和不大于n的最大个数元素
    a.sort()
    s = 0
    index = 0
    if n < a[0]:
        return -1
    while s < n and index <len(a):
        s += a[index]
        index += 1
    return index
     
def sub_list(a, index, n):  # 生成元素个数为n的子数组
    if index == n:
        res = a[:n]
        res.sort()
        global last
        if res not in last:
            last.append(res)
        left_0 = a[n:]
        left_0.sort()
        global left
        if left_0 not in left:
            left.append(left_0)
    else:
        for i in range(index, len(a)):
            a[i], a[index] = a[index], a[i]
            sub_list(a, index + 1, n)
            a[index], a[i] = a[i], a[index]

def main(a, n):   
    result = dict()
    mx = max_num(a, n)
    if mx == len(a):
        result[str(a)] = n - sum(a)
        return result
    if mx ==-1:
        return {}
    for i in range(1, mx+1):
        sub_list(a, 0, i)
    global last
    global left
    for i in range(len(last)):
        if sum(last[i]) + min(left[i]) > n and sum(last[i]) <= n:    # 筛选标准
            result[str(last[i])] = n - sum(last[i])
        else:
            pass
    return sort_dict(result)

a= [1,2,3,4,5,6,7,8,9,10]
n=120
res = main(a, n)
print(res)
n=0
res = main(a, n)
print(res)
n=14
res = main(a, n)
print(res)
last = []
left = []

def sort_dict(last)