题目地址：

https://www.lintcode.com/problem/k-sum-iii/description

给定一个正整数数组$A$，再给定一个正整数$k$和一个目标值$t$，允许从$A$中挑$k$个数，问有多少个方案使得挑出的数字和为$t$。挑出的数的奇偶性一定要相同。两种挑法，只要有数的下标不一样，就视为不同的挑法，即使挑出的数字数值一样。

思路是DFS。先将$A$中的所有奇数和偶数分开来，各自加入两个列表里，然后对每个列表进行DFS，枚举其$k$子集，遇到和等于$t$的时候就累加答案即可。这里可以考虑若干剪枝的方法，比如，可以先对列表进行由大到小的排序，先枚举大的数，有利于快速排除掉分支较少的叉；此外，如果发现某个数大到其加上列表最小值都大于$t$了，那这个数当然不可能与别人加起来等于$t$，可以直接略过；还有，如果接下来枚举的时候，还剩下的数的个数少于了$k$减去已经枚举的数了，那可以直接剪枝返回。代码如下：

import java.util.ArrayList; import java.util.List; public class Solution { /** * @param a: the array a * @param k: the integer k * @param target: the integer target * @return: return the number of legal schemes */ public int getAns(int[] a, int k, int target) { // write your code here List<Integer> odds = new ArrayList<>(), evens = new ArrayList<>(); for (int i = 0; i < a.length; i++) { if (a[i] % 2 != 0) { odds.add(a[i]); } else { evens.add(a[i]); } } // 逆序排序，并略过太大的数 odds.sort((x, y) -> -Integer.compare(x, y)); int posOdd = 0; while (posOdd < odds.size() && odds.get(posOdd) + odds.get(odds.size() - 1) > target) { posOdd++; } evens.sort((x, y) -> -Integer.compare(x, y)); int posEven = 0; while (posEven < evens.size() && evens.get(posEven) + evens.get(evens.size() - 1) > target) { posEven++; } return dfs(posOdd, 0, target, odds, 0, k) + dfs(posEven, 0, target, evens, 0, k); } // 已经枚举了count个数和为sum，接下来从list[pos]开始枚举，返回恰好找到k个数和为target的方案数 private int dfs(int pos, int sum, int target, List<Integer> list, int count, int k) { // 如果已经枚举了k个数了，此时如果sum恰好等于target，那就说明找到了一个方案，返回1；否则返回0 if (count == k) { if (sum == target) { return 1; } return 0; } // 枚举到列表尾还没发现合法的解，返回0 if (pos == list.size()) { return 0; } int res = 0; // 如果还剩下的数的个数大于等于k - 已经枚举的数，则进行枚举 for (int i = pos; i + (k - count) <= list.size(); i++) { if (sum + list.get(i) <= target) { res += dfs(i + 1, sum + list.get(i), target, list, count + 1, k); } } return res; } }

时间复杂度$O(o\log o+e\log e+(\genfrac{}{}{0ex}{}{o}{k})+(\genfrac{}{}{0ex}{}{e}{k}))$，空间$O(n)$。