【Lintcode】1689. k Sum III

【Lintcode】1689. k Sum III

题目地址：

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

思路是DFS。先将 A A A中的所有奇数和偶数分开来，各自加入两个列表里，然后对每个列表进行DFS，枚举其 k k k子集，遇到和等于 t t t的时候就累加答案即可。这里可以考虑若干剪枝的方法，比如，可以先对列表进行由大到小的排序，先枚举大的数，有利于快速排除掉分支较少的叉；此外，如果发现某个数大到其加上列表最小值都大于 t t t了，那这个数当然不可能与别人加起来等于 t t t，可以直接略过；还有，如果接下来枚举的时候，还剩下的数的个数少于了 k k 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 hereList<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) -> -Integerpare(x, y));int posOdd = 0;while (posOdd < odds.size() && (posOdd) + (odds.size() - 1) > target) {posOdd++;}evens.sort((x, y) -> -Integerpare(x, y));int posEven = 0;while (posEven < evens.size() && (posEven) + (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；否则返回0if (count == k) {if (sum == target) {return 1;}return 0;}// 枚举到列表尾还没发现合法的解，返回0if (pos == list.size()) {return 0;}int res = 0;// 如果还剩下的数的个数大于等于k - 已经枚举的数，则进行枚举for (int i = pos; i + (k - count) <= list.size(); i++) {if (sum + (i) <= target) {res += dfs(i + 1, sum + (i), target, list, count + 1, k);}}return res;}
}

时间复杂度 O ( o log ⁡ o + e log ⁡ e + ( o k ) + ( e k ) ) O(olog o+elog e+{ochoose k}+{echoose k}) O(ologo+eloge+(ko​)+(ke​))，空间 O ( n ) O(n) O(n)。