k Sum II.java

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
        if (A == null || A.length == 0) {
            return null;
        }
        
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> ksum = new ArrayList<Integer>();
        
        kSumIIHelper(A, k, 0, target, result, ksum);
        
        return result;
    }
    
    public void kSumIIHelper(int[] A, int k, int pos, int target, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> ksum) {
        if (ksum.size() == k) {
            if (target == 0) {
                result.add(new ArrayList<Integer>(ksum));
                return;
            }
        }

        for (int i = pos; i < A.length; i++) {
            if (A[i] <= target) {
                ksum.add(A[i]);
                int tempTarget = target - A[i];
                kSumIIHelper(A, k, i + 1, tempTarget, result, ksum);
                ksum.remove(ksum.size() - 1);
            }
        }
    }
}