从23个已知数中取n个数，n个数之和是250430，求是哪几个数之和

Question

一共有23个已知数字，然后里面n个数之和是250430，n未知，现在需要知道是由哪几个数字组成了250430这个总数，只需要这个结果就行了，最好把代码也能给我，编程语言不限。证明不存在这个可能的话也可以。
23个已知数字：
20375
34665
26925
25060
22185
24375
22680
19195
19675
9800
10280
20090
22070
18765
18810
19180
15070
23000
18650
17320
21135
22440
18175

Answer 1

先排序，然后深度优先。

nums = [20375,34665,26925,25060,
22185,24375,22680,19195,
19675,9800,10280,20090,
22070,18765,18810,19180,
15070,23000,18650,17320,
21135,22440,18175]

tar = 250430

def dfs(tar,nums,res):
    if sum(res)==tar:
        return res
    elif len(nums)<1 or sum(res)>tar:
        return False
    else:
        for i in range(len(nums)):
            temp = dfs(tar,nums[i+1:],res+[nums[i]])
            if temp: return temp
            elif temp==False: break

nums = sorted(nums)
print(dfs(tar,nums,list()))

结果

[9800, 10280, 15070, 17320, 18175, 18650, 18765, 19180, 20090, 20375, 21135, 26925, 34665]

要找出所有的解，只要稍微改一下：

def dfs(tar,nums,res):
    if sum(res)==tar:
        all_res.append(res)
    elif len(nums)<1 or sum(res)>tar:
        return False
    else:
        for i in range(len(nums)):
            temp = dfs(tar,nums[i+1:],res+[nums[i]])
            if temp==False: break

nums = sorted(nums)
all_res=[]
dfs(tar,nums,list())
print(len(all_res))
print(sorted(all_res,key=len)[0])

可以看到总共有323种解，n最少的解是

323
[15070, 18175, 18765, 20090, 22185, 22440, 22680, 24375, 25060, 26925, 34665]