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. Return: [ [1,4], [2,3] ] Tags LintCode Copyright Depth First Search
public ArrayList<ArrayList<Integer>> kSumII(int[] A, int k, int target) {
// write your code here
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
if (A == null || k > A.length) {
ans.add(list);
return ans;
}
Arrays.sort(A);
dfs(ans, list, A, k, target, 0);
return ans;
}
private void dfs(ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> list, int[] A, int k, int target, int pos) {
if (k == 0 && target == 0) {
ans.add(new ArrayList(list));
return;
}
if (target < 0 || pos >= A.length || pos + k > A.length) {
return;
}
for (int i = pos; i < A.length; i++) {
list.add(A[i]);
dfs(ans, list, A, k - 1, target - A[i], i + 1);
list.remove(list.size() - 1);
}
}
原文：http://www.cnblogs.com/apanda009/p/7294274.html