1689. k Sum III

class Solution { public: /** * @param a: the array a * @param k: the integer k * @param target: the integer target * @return: return the number of legal schemes */ int getAns(vector<int> &a, int k, int target) { // write your code here vector<int> odds; vector<int> evens; for(auto i : a){ if(i % 2){ odds.push_back(i); } else{ evens.push_back(i); } } int num1 = 0, num2 = 0; if(k <= odds.size()){ num1 = getNum(odds, k, target); } if(k <= evens.size()){ num2 = getNum(evens, k, target); } return num1 + num2; } int getNum(vector<int> &a, int k, int target){ if(k > a.size()){ return 0; } int cnt = 0; dfs(a, k, target, cnt, 0, 0, 0); return cnt; } void dfs(vector<int> &a, int k, int target, int &cnt, int sum, int elemNum, int start){ if(sum == target){ if(elemNum == k){ cnt++; } return; } if(sum > target || start == a.size() || elemNum > k){ return; } for(int i = start; i < a.size(); i++){ dfs(a, k, target, cnt, sum + a[i], elemNum + 1, i + 1); } return; } };