k Sum II

Java

//连续搜索
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) {
        	List<List<Integer>> res = new ArrayList<>();
        	dfs(A, k, 0, target, new ArrayList<Integer>(), res);
        	return res;
    }
    
    private void dfs(int[] nums, int k, int index, int target, List<Integer> path, List<List<Integer>> res) {
        if (k == 0) {
        if (target == 0) {
        res.add(new ArrayList<>(path));	
        }
        return;
        }
        
        if (target <0 || index == nums.length) return;
        
        path.add(nums[index]);
        dfs(nums, k - 1, index + 1, target - nums[index], path, res);
        path.remove(path.size() - 1);
        dfs(nums, k, index + 1, target, path, res);
    }
}


//跳跃搜索dfs
private void dfs(int[] nums, int k, int index, int target, List<Integer> path, List<List<Integer>> res) {
    if (k == 0) {
    if (target == 0) {
    res.add(new ArrayList<>(path));	
    }
    return;
    }
    
    if (target <0) return; //这个地方算是减枝，并不算是递归出口
    
    for (int i = index; i < nums.length; i++) {
        path.add(nums[i]);
        dfs(nums, k - 1, i + 1, target - nums[i], path, res);
        path.remove(path.size() - 1);	
    }
}