LintCode 90 K Sum II

思路

dfs搜索，与Combination Sum的区别是多了一个限制：每个答案的长度为k。对于这种问题，只需要在dfs的传入参数列表中增加这个限制，并且相应修改递归出口。
时间复杂度O(2^n)
空间复杂度O(logn)

代码

public class Solution {
    /** @param A: an integer array* @param k: a postive integer <= length(A)* @param target: an integer* @return: A list of lists of integer*/public List<List<Integer>> kSumII(int[] A, int k, int target) {
    // write your code hereList<List<Integer>> results = new ArrayList<>();dfs(A, k, target, 0, new ArrayList<>(), results);return results;}private void dfs(int[] nums,int k,int target,int startIndex,List<Integer> combination,List<List<Integer>> results) {
    if (target == 0 && k == 0) {
    results.add(new ArrayList<>(combination));return;}if (target < 0 || k < 0) {
    return;}for (int i = startIndex; i < nums.length; i++) {
    combination.add(nums[i]);dfs(nums, k - 1, target - nums[i], i + 1, combination, results);combination.remove(combination.size() - 1);}}
}