从23个已知数中取n个数，n个数之和是250430，求是哪几个数之和
一共有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
先排序，然后深度优先。
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]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Created with IntelliJ IDEA.
*
* @author 广大菜鸟
* @since 2022/7/17 17:37
* E-mail: 1456084073@qq.com
*/
public class Solution {
public static List<Integer> res ;
public static void main(String[] args) {
int[]datas = {
20375
,34665
,26925
,25060
,22185
,24375
,22680
,19195
,19675
,9800
,10280
,20090
,22070
,18765
,18810
,19180
,15070
,23000
,18650
,17320
,21135
,22440
,18175
};
int target = 250430;
res = new ArrayList<>();
Arrays.sort(datas);
if(target<datas[0]){
System.out.println("no answer");
return;
}
int startIndex = datas.length-1;
while(datas[startIndex] > target){
startIndex -= 1;
}
boolean is = dfs(datas, startIndex, target);
if(is){
for (Integer re : res) {
System.out.print(re + " ");
}
}else{
System.out.println("no answer");
}
}
private static boolean dfs(int[]datas, int index, int target){
if(index<0){
return false;
}
for(int i=index;i>=0;i--){
if(target>datas[i]){
boolean is = dfs(datas, i-1, target-datas[i]);
if(is){
res.add(datas[i]);
return true;
}
}else if(target == datas[i]){
res.add(datas[i]);
return true;
}
}
return false;
}
}
#include <iostream>
using namespace std;
int f[25][255000],st[25],num[25];
int n;
const int N = 250430;
bool dp()
{
f[0][0] = 1;
for(int i = 1;i <= n;i ++)
for(int j = 0;j <= N - num[i];j ++)
if (f[i - 1][j])
{
f[i][j] = 1; //当前数字不取
f[i][j + num[i]] = 1; //当前数字取
}
if (!f[n][N]) return false;
int last = N;
for(int i = n;i;i --)
if (last >= num[i] && f[i - 1][last - num[i]]) //当前数字取了
{
st[i] = 1;
last -= num[i];
}
return true;
}
bool dfs(int now,int sum)
{
if (sum == N)
return true;
if (sum > N)
return false;
if (now > n) //搜索完毕并且sum不是N
return false;
st[now] = 1;
bool t = dfs(now + 1,sum + num[now]); //搜索取当前数字的方案
if (t) return t;
st[now] = 0;
return dfs(now + 1,sum); //否则不取当前数字
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++)
cin >> num[i];
bool t;
//t = dp();
t = dfs(1,0);
if (! t)
{
puts("impossible");
return 0;
}
for(int i = 1;i <= n;i ++)
if (st[i]) cout << num[i] << ' ';
return 0;
}
/*
23
20375
34665
26925
25060
22185
24375
22680
19195
19675
9800
10280
20090
22070
18765
18810
19180
15070
23000
18650
17320
21135
22440
18175
*/
用了两种方法，一种是背包问题求解，复杂度是O(250430*n)
另一种是深度优先搜索，复杂度是O(2^n)，但由于进行剪枝，跑不满，实际情况会快很多。不过n再大点，推荐用背包。
然后main函数里面，dp和dfs对应两种做法，一次运行一个就行，把另一个注释掉。
得到的结果分别是34665 26925 22680 10280 20090 15070 23000 18650 17320 21135 22440 18175
20375 34665 26925 25060 22185 24375 22680 19195 18765 15070 21135
计算器验算无误。
dp做法更偏好靠近后面的数字（因为我是从后往前判断取不取）
深搜做法更偏好靠前的数字（因为一旦成立就开始return）
一定要先给 nums 数组排序；
一定要先给 nums 数组排序；
一定要先给 nums 数组排序；
答案不唯一，随便选了几个：
n=11时，是 26925, 34665, 25060, 24375, 22680, 22440, 22185, 20090, 18765, 18175, 15070
n=12时，是26925, 34665, 25060, 23000, 22680, 22440, 22185, 19675, 18650, 15070, 10280, 9800
n=13时，是26925, 34665, 21135, 20375, 20090, 19180, 18765, 18650, 18175, 17320, 15070, 10280, 9800
【参考代码】
import java.util.ArrayList;
import java.util.Arrays;
/**
* @author yangbocsu
* @create 2022/06/9:10
* @projectName test1
*/
public class Solution {
public static void main(String[] args) {
int[] nums = {20375,34665,26925,25060,22185,24375,22680,19195,19675,9800,10280,20090,22070,18765,18810,19180,15070,23000,18650,17320,21135,22440,18175};
int target = 250430;
Arrays.sort(nums);
for (int i = 2; i < 23; i++) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
res = nSumTarget(nums, i, 0, target);
if (res.size() > 0){
System.out.println("-------- n="+ i +"----------------");
System.out.println(res.toString());
}
}
}
public static ArrayList nSumTarget(int[] nums,int n,int start,int target){
int sz = nums.length;
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
// 至少是 2Sum，且数组大小不应该小于 n
if (n < 2 || sz < n)
return res;
// 2Sum 是 base case
if (n == 2){
// 双指针那一套操作
int lo = start, hi = sz - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
ArrayList<Integer> tmp = new ArrayList<>();
tmp.add(left);
tmp.add(right);
res.add(tmp);
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
} else {
// n > 2 时，递归计算 (n-1)Sum 的结果
for (int i = start; i < sz; i++) {
ArrayList<ArrayList<Integer>>sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for (ArrayList<Integer>arr : sub) {
// (n-1)Sum 加上 nums[i] 就是 nSum
arr.add(nums[i]);
res.add(arr);
}
while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
}
}
return res;
}
}
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans_lists = []
try_list = []
def dfs(target, idx):
if idx == len(candidates) or target<0:
return
if target == 0:
ans_lists.append(try_list[:])
return
dfs(target, idx+1)
if target - candidates[idx] >= 0:
try_list.append(candidates[idx])
dfs(target - candidates[idx], idx)
try_list.pop()
dfs(target, 0)
return ans_lists