LintCode 1689. k求和III（递归）

样例 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

class Solution {
    int sum = 0;
    int t;
public:
    int getAns(vector<int> &a, int k, int target) {
        if(target <= 0)
            return 0;
        t = target;
        vector<int> odd, even;
        for(auto& ai : a)
        {
            if(ai%2)
                odd.push_back(ai);
            else
                even.push_back(ai);
        }
        dfs(odd,0,0,0,k);
        dfs(even,0,0,0,k);
        return sum;
    }

    void dfs(vector<int> &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,i+1,count+1,s+v[i],k);
        }
    }
};