蓝桥杯学习|部分和（dfs）蓝桥杯学习|C

蓝桥杯练习034 部分和题目描述
给定整数序列a1,a2,…,an,判断是否可以从中选出若干数,使它们的和恰好为k.

1≤n≤20-10^8≤ai≤10^8-10^8≤k≤10^8

样例:
输入

4 1 2 4 7 13

【蓝桥杯学习|部分和（dfs）】输出:

Yes (13=2+4+7)

解题思路

1.通过对输入数据的取与不取来凑k 2.对每一个位置上的元素都可以取或者不取 3.可以先考虑取第一个位置的元素，此时剩余k-a[0]还需要从剩余元素中取 4.然后考虑下一个位置 5.当k小于0或者数组下标越界时要返回上一次的位置 6.当k恰好为0时说明已经找到了满足的方式，根据要求输出结果 7.需要注意的是：不选cur位置元素的时候，dfs后要将该元素加入vec中便于下次搜索要这个元素的情况 8.最后要回溯。将加入的元素删除

代码

#include #include #include using namespace std; int kk; void dfs(int a[],int n,int k,int cur,vector v){ if(k==0){//找到满足的值 cout<<"Yes("<>n; int a[n]; vector vec; for(int i=0; i>a[i]; cin>>k; kk=k; //保存k的值，便于输出状态 dfs(a,n,k,0,vec); return 0; }