本文摘要：该题要求从包含N个正整数的数组A中寻找若干个数，使得它们之和恰好为给定值K。采用深度优先搜索(DFS)策略，针对不超过20个元素的数据规模，实现O(2^n)复杂度的解决方案，并在实际编程中注意搜索起点应为(0,0)以覆盖所有可能的选择情况。此外，尽管数据量不大，也有解题者提出运用背包问题的思路，通过动态规划(DP)解决，但由于每个物品体积与价值相等，可简化为处理恰好装满背包的情形。最终根据搜索结果输出Yes或No，以判断是否存在满足条件的子集。

转载文章

本篇文章为转载内容。原文链接：https://xuanweiace.blog.csdn.net/article/details/83115964。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

题干：

给出N个正整数组成的数组A，求能否从中选出若干个，使他们的和为K。如果可以，输出："Yes"，否则输出"No"。

Input

第1行：2个数N, K, N为数组的长度, K为需要判断的和(2 <= N <= 20，1 <= K <= 10^9)
第2 - N + 1行：每行1个数，对应数组的元素Aii (1 <= Aii <= 10^6)

Output

如果可以，输出："Yes"，否则输出"No"。

Sample Input

Sample Output

No

解题报告：

很多人说这题用背包，，，但是我一直想不通，1e9的空间，是怎么用的背包。。。这题数据量20，显然是搜索啊，，，复杂度o(2^n)不怂，不到30行就搞定了。

如果要写背包的话思路上也是可以的，因为每个背包体积1e6，20个加起来也才2e8，并且dp[j]=val，这里可以保证jval<=j，因为物品的体积和价值是相同的啊。所以直接跑恰好装满问题，并且dp[k]=k就可以了。只要数组开的下，，背包也不难写。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k;
ll a[55];
bool dfs(ll step,ll cur) {if(cur  == k) return 1;if(step == n) return 0;if(cur+a[step+1] <= k) {if(dfs(step+1,cur+a[step+1])) return 1;}if(dfs(step+1,cur)) return 1;return 0;
}
int main()
{cin>>n>>k;for(int i = 1; i<=n; i++) cin>>a[i];sort(a+1,a+n+1); if(dfs(0,0)) puts("Yes");else puts("No");return 0 ;
}

总结：搜索题一定要注意啊，需要从(0,0)这个状态开始搜索，因为你直接(1,a[1])传入参数了，那不选第一个数这个状态就被没有搜啊。。。

本篇文章为转载内容。原文链接：https://xuanweiace.blog.csdn.net/article/details/83115964。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

名词解释

作为当前文章的名词解释，仅对当前文章有效。

深度优先搜索(DFS)：在图论与计算机科学中，深度优先搜索是一种用于遍历或搜索树或图的算法。它通过递归地访问相邻节点深入探索每个分支，直到达到某个条件（例如找到目标节点、无法继续深入等）才回溯至前一个节点并尝试其他分支。在这个问题场景下，DFS被用来遍历所有可能的选择子集，检查是否存在一个子集使得其元素之和等于给定的目标值K。

动态规划(DP)：动态规划是一种通过将复杂问题分解为多个重叠子问题，并存储这些子问题的解以避免重复计算，从而求解最优化问题的方法。文中提及的背包问题可以使用动态规划来解决，尤其是当物品的价值等于体积时，可以简化为恰好装满背包的状态转移方程，判断是否能组合出总价值（或体积）为K的可行解。

背包问题：背包问题是一个经典的计算机科学与运筹学中的组合优化问题。给定一组物品，每种物品都有一定的价值和重量（或体积），目标是选择一些物品放入容量有限的背包中，使得背包内物品的总价值最大（或者在特定约束条件下满足特定的总价值要求）。本文中的特殊情况是，由于物品的体积和价值相等，背包问题转化为寻找能否恰好填满背包到指定容量（即目标和K）。

[转载]【51Nod - 1268】和为K的组合 （背包 或 dfs）

[转载]【51Nod - 1268】和为K的组合（背包或 dfs）