k Sum II
Written on October 21, 2015
Tweet
Given n unique integers, number k (1<=k<=n) and target. Find all possible k integers where their sum is target.
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) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (A == null || A.length == 0) return result;
ArrayList<Integer> path = new ArrayList<Integer>();
helper(A, k, target, 0, path, result);
return result;
}
public void helper(int[] A, int k, int target, int start, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result) {
if (k < 0) return;
if (k == 0 && target == 0) {
result.add(new ArrayList<Integer> (path));
return;
}
for (int i = start; i < A.length; i++) {
path.add(A[i]);
helper(A, k - 1, target - A[i], i + 1, path, result);
//bug i + 1 not start + 1
path.remove(path.size() - 1);
}
}
}//dfs and back tracking