## Thursday, May 12, 2016

### Lintcode: K Sum I

Related: Lintcode K Sum II
http://www.cnblogs.com/yuzhangcmu/p/4279676.html
http://www.jiuzhang.com/solutions/k-sum/
https://github.com/yuzhangcmu/LeetCode/blob/master/lintcode/dp/KSum.java
Given n distinct positive integers, integer k (k <= n) and a number target. Find k numbers where sum is target.
Calculate how many solutions there are?
```    public int  kSum1(int A[], int k, int target) {
9         if (target < 0) {
10             return 0;
11         }
12
13         int len = A.length;
15         int[][][] D = new int[len + 1][k + 1][target + 1];
16
17         for (int i = 0; i <= len; i++) {
18             for (int j = 0; j <= k; j++) {
19                 for (int t = 0; t <= target; t++) {
20                     if (j == 0 && t == 0) {
21                         // select 0 number from i to the target: 0
22                         D[i][j][t] = 1;
23                     } else if (!(i == 0 || j == 0 || t == 0)) {
24                         D[i][j][t] = D[i - 1][j][t];
25                         if (t - A[i - 1] >= 0) {
26                             D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]];
27                         }
28                     }
29                 }
30             }
31         }
32
33         return D[len][k][target];
34     }```

D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]];

1. 如果你从左往右按列计算，每一列会被重复地加总，就会有重复计算。我们可以想象一下，len = 0为上表，len = 1为下表。

len = 0 那张表留下的值，下一个值的计算就不会准确了。
2. 或者如果你逐行计算，也是不可以的。因为你也是把生成D[j][t](在图里写的是D[i][j])的被sum的区域覆盖，也会造成结果不准确。
3. 所以，只要我们逐列计算，并且顺序是从右往左，即使我们只有一个二维表，我们的被sum区域也可以保持洁净，从空间角度来想，

``` 1 // 2 dimension
2     public int  kSum(int A[], int k, int target) {
4         if (target < 0) {
5             return 0;
6         }
7
8         int len = A.length;
9
10         // D[i][j]: k = i, target j, the solution.
11         int[][] D = new int[k + 1][target + 1];
12
13         // only one solution for the empty set.
14         D[0][0] = 1;
15         for (int i = 1; i <= len; i++) {
16             for (int t = target; t > 0; t--) {
17                 for (int j = 1; j <= k; j++) {
18                     if (t - A[i - 1] >= 0) {
19                         D[j][t] += D[j - 1][t - A[i - 1]];
20                     }
21                 }
22             }
23         }
24
25         return D[k][target];
26     }```

https://github.com/yuzhangcmu/LeetCode/blob/master/lintcode/dp/KSum.java
public int  kSum(int A[], int k, int target) {
if (target < 0) {
return 0;
}

int len = A.length;

// D[i][j]: k = i, target j, the solution.
int[][] D = new int[k + 1][target + 1];

// only one solution for the empty set.
D[0][0] = 1;
for (int i = 1; i <= len; i++) {

for (int j = 1; j <= k; j++) {
for (int t = target; t > 0; t--) {
if (t - A[i - 1] >= 0) {
D[j][t] += D[j - 1][t - A[i - 1]];
}
}
}
}

return D[k][target];
}

X. DFS
http://blog.csdn.net/wankunde/article/details/44058097

public int kSum(int A[], int k, int target) { if (A.length < k || k == 0) return 0; if(k == 1){ for(int i=0;i<A.length;i++) if(A[i] == target) return 1; return 0; } else { int[] B = new int[A.length - 1]; if (A.length > 1) System.arraycopy(A, 1, B, 0, A.length - 1); return kSum(B, k - 1, target - A[0]) + kSum(B, k, target); } }
http://blog.welkinlan.com/2015/08/20/k-sum-i-ii-lintcode-java/
We can use backtracking to solve this problem, which is O(n^k). However, this is TLE    public int kSum(int A[], int k, int target) {
ArrayList<Integer> result = new  ArrayList<Integer>();
if (A == null || A.length == 0) {
return 0;
}
helper(A, k, target, result, 0, new ArrayList<Integer>());
return result.get(0);
}

private void helper(int A[], int k, int target, ArrayList<Integer> result, int curIndex, ArrayList<Integer> curList) {
if (curList.size() == k) {
if (target == 0) {
result.set(0, result.get(0) + 1);
}
return;
}
for (int i = curIndex; i < A.length; i++) {
helper(A, k, target - A[i], result, i + 1, curList);
curList.remove(curList.size() - 1);
}
}
http://codeanytime.blogspot.com/2014/12/lintcode-k-sum.html
``````    void helper(vector<int> A,int k, int start,int target, int & ans) {
if (k < 0 || target < 0) return;
if (k == 0 && target == 0) {
ans++;
return;
}
for(int i = start; i <= A.size()-k; i++)
helper(A, k-1, i+1, target - A[i], ans);
}
int solutionKSum(vector<int> A,int k,int target) {
int ans = 0;
helper(A, k, 0, target, ans);
return ans;
}``````

sum < k,
sum = k,
sum > k,