Related: Lintcode: K Sum I
https://zhengyang2015.gitbooks.io/lintcode/k_sum_ii_90.html
X. https://leetcode.com/problems/4sum/discuss/8609/My-solution-generalized-for-kSums-in-JAVA
https://richdalgo.wordpress.com/2015/01/29/lintcode-k-sum-ii/
O(N^(K-1)).
https://lefttree.gitbooks.io/leetcode/content/CombinationandPermutation/kSum2.html
http://www.jianshu.com/p/d05cc2ecb975
https://zhengyang2015.gitbooks.io/lintcode/k_sum_ii_90.html
Given n unique integers, number k (1<=k<=n) and target.
Find all possible k integers where their sum is target.
Example
Given [1,2,3,4], k = 2, target = 5. Return:
[ [1,4],
[2,3] ]
X. https://leetcode.com/problems/4sum/discuss/8609/My-solution-generalized-for-kSums-in-JAVA
If you have already read and implement the 3sum and 4sum by using the sorting approach: reduce them into 2sum at the end, you might already got the feeling that, all ksum problem can be divided into two problems:
- 2sum Problem
- Reduce K sum problem to K – 1 sum Problem
Therefore, the ideas is simple and straightforward. We could use recursive to solve this problem. Time complexity is O(N^(K-1)).
public class Solution {
int len = 0;
public List<List<Integer>> fourSum(int[] nums, int target) {
len = nums.length;
Arrays.sort(nums);
return kSum(nums, target, 4, 0);
}
private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
if(index >= len) {
return res;
}
if(k == 2) {
int i = index, j = len - 1;
while(i < j) {
//find a pair
if(target - nums[i] == nums[j]) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(target-nums[i]);
res.add(temp);
//skip duplication
while(i<j && nums[i]==nums[i+1]) i++;
while(i<j && nums[j-1]==nums[j]) j--;
i++;
j--;
//move left bound
} else if (target - nums[i] > nums[j]) {
i++;
//move right bound
} else {
j--;
}
}
} else{
for (int i = index; i < len - k + 1; i++) {
//use current number to reduce ksum into k-1sum
ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k-1, i+1);
if(temp != null){
//add previous results
for (List<Integer> t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
while (i < len-1 && nums[i] == nums[i+1]) {
//skip duplicated numbers
i++;
}
}
}
return res;
}
} 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> list = new ArrayList<Integer>();
Arrays.sort(A);//\\
helper(result, list, A, k, target, 0);
return result;
}
private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] A, int k, int target, int pos){
if(k == 0 && target == 0){
result.add(new ArrayList<Integer>(list));
return;
}
if(k > 0 && target > 0){
for(int i = pos; i < A.length; i++){
if(A[i] > target){//\\
return;
}
list.add(A[i]);
helper(result, list, A, k - 1, target - A[i], i + 1);
list.remove(list.size() - 1);
}
}
}X. DFS
public ArrayList<ArrayList<Integer>> kSumII(int A[], int k, int target) { 10 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 11 ArrayList<Integer> path = new ArrayList<Integer>(); 12 helper(res, path, A, k, target, 0); 13 return res; 14 } 15 16 public void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> path, int[] A, int k, int remain, int index) { 17 if (path.size() == k) { 18 if (remain == 0) { 19 res.add(new ArrayList<Integer>(path)); 20 } 21 return; 22 } 23 for (int i=index; i<A.length; i++) { 24 path.add(A[i]); 25 helper(res, path, A, k, remain-A[i], i+1); 26 path.remove(path.size()-1); 27 } 28 }29 }
https://richdalgo.wordpress.com/2015/01/29/lintcode-k-sum-ii/
def kSumII(self, A, k, target): result = [] self.dfs(A, k, 0, target, [], result) return resultdef dfs(self, A, k, index, target, tmp, result): if k == 0: if target == 0: result.append(tmp[:]) else: for j in range(index, len(A)): tmp.append(A[j]) self.dfs(A, k - 1, j + 1, target - A[j], tmp, result) tmp.pop()https://lefttree.gitbooks.io/leetcode/content/CombinationandPermutation/kSum2.html
ArrayList<ArrayList<Integer> > ans; public void dfs(int A[], int K, int target, int index, ArrayList<Integer> tans) { if(K == 0 && target == 0) { ans.add(new ArrayList<Integer>(tans)); return ; } if(K < 0 || target < 0 || index < 0) return ; dfs(A, K, target, index - 1, tans); tans.add(A[index]); dfs(A, K - 1, target - A[index], index - 1, tans); tans.remove(tans.size() - 1); } public ArrayList<ArrayList<Integer>> kSumII(int A[], int K, int target) { ans = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> tans = new ArrayList<Integer>(); dfs(A, K, target, A.length - 1, tans); return ans; }
- 由于k Sum是求个数，所以考虑动态规划，直接DFS会超时。而k Sum II 是求所有具体的解，所以直接DFS.
- 思路跟 subsets 类似，可以想象成求一些特殊的subsets，加入result时，要符合subset的和等于target
