建一个网站的流程,二手车网站设计,小程序制作一个需要多少钱?,html5网站开发1. 题目
给出 n 个正整数和整数 k 以及一个目标数字 target.
在 n 个数中找出 k 个奇数 或 k 个偶数 使得和为target#xff0c;输出方案数
样例 1:
给出 [1,2,3,4], k 2,target 4, 返回 1
输入:
[1,2,3,4]
2
4
输出:
1
解释:
只有一个方案#xff1a;[1,3].样例 2:
给…1. 题目
给出 n 个正整数和整数 k 以及一个目标数字 target.
在 n 个数中找出 k 个奇数 或 k 个偶数 使得和为target输出方案数
样例 1:
给出 [1,2,3,4], k 2,target 4, 返回 1
输入:
[1,2,3,4]
2
4
输出:
1
解释:
只有一个方案[1,3].样例 2:
给出 [9,1,4,4], k 3,target 46, 返回 0
输入:
[9,1,4,4]
3
46
输出:
0注意事项 1≤n≤201≤n≤201≤n≤20 k≤nk≤nk≤n n个数里面可能有重复的数 对于数值均对应相同的两个方案只要存在不同的下标便可以视作两个不同方案
2. 解题
拆分出奇偶数组对两个数组分别递归
class Solution {int sum 0;int t;
public:int getAns(vectorint a, int k, int target) {if(target 0)return 0;t target;vectorint odd, even;for(auto ai : a){if(ai%2)odd.push_back(ai);elseeven.push_back(ai);}dfs(odd,0,0,0,k);dfs(even,0,0,0,k);return sum;}void dfs(vectorint v, int idx, int count, int s,int k){if(s t || count k){if((s t) (count k))sum;return;}for(int i idx; i v.size(); i){dfs(v,i1,count1,sv[i],k);}}
};100% 数据通过测试 总耗时 50 ms 您的提交打败了 38.46% 的提交!
