k Sum II

Given n unique integers, number k (1<=k<=n)  and target. Find all possible k integers where their sum is target.

Have you met this question in a real interview? 

Yes

Example

Given [1,2,3,4], k=2, target=5, [1,4] and [2,3] are possible solutions.

public class Solution {

    /**

     * @param A: an integer array.

     * @param k: a positive integer (k <= length(A))

     * @param target: a integer

     * @return a list of lists of integer 

     */ 

    public ArrayList<ArrayList<Integer>> kSumII(int A[], int k, int target) {

        // write your code here

        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

        dfs(A, 0, new ArrayList<Integer>(), res, k, target);

        return res;

        

    }

    

    private void dfs(int A[], int start, ArrayList<Integer> sub, ArrayList<ArrayList<Integer>> res, int k, int target){

        

        if(k < 0 || target < 0) return;

        if(k == 0 && target == 0){

            res.add(new ArrayList<Integer>(sub));

            return;

        }

        

        for(int i = start; i < A.length; i++){

            sub.add(A[i]);

            dfs(A, i+1, sub, res, k-1, target-A[i]);

            sub.remove(sub.size()-1);

        }

        

    }

    

    

}