Massive Algorithms: Lintcode: K Sum I

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     }

我们可以把最外层的Matrix可以省去。

这里最优美的地方，在于我们把target作为外层循环，并且从右往左计算。这里的原因是：

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

这个表达式说明D[i][j][t]是把上一级i的结果累加过来。这里我们省去了i这一级，也就是说在D[j][t]这个表里就地累加。而且t - A[i - 1]小于t。

在以下图表示就是说D[j][t]是来自于上一行的在t左边的这些值中挑一些加起来。

所以我们就必须从右往左逐列计算来避免重复的累加。

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

现在我们只有一个表，就是下面这个（因为第一个维度被取消了），现在如果你从左往右计算，被sum的区域会被填掉，覆盖

len = 0 那张表留下的值，下一个值的计算就不会准确了。

2. 或者如果你逐行计算，也是不可以的。因为你也是把生成D[j][t](在图里写的是D[i][j])的被sum的区域覆盖，也会造成结果不准确。

3. 所以，只要我们逐列计算，并且顺序是从右往左，即使我们只有一个二维表，我们的被sum区域也可以保持洁净，从空间角度来想，

就相当于从len=0那张表中取值。

总结：这种思维方式可能在面试里很难遇到，不过，可以开拓我们思维，这里同样是动规时如果取得上一级的值的问题，并且它考虑了省

去一级，就地利用二维空间的值，那么就要考虑我们上一级的旧表不要被覆盖。可以在大脑中构思一个三维空间，一个三维表由多个二维

表构成，如果把它们用一个表来做，再思考一下即可。

 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://www.jiuzhang.com/solution/k-sum/

https://github.com/yuzhangcmu/LeetCode/blob/master/lintcode/dp/KSum.java
public int kSum(int A[], int k, int target) {
// write your code here
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
思路一：迭代，开始时依次选择一个点，然后根据新的target值和新的数组，选择k-1个数，思路直接简单。但是存在重复计算。该算法复杂度为 Nk ,指数递增，所以在lintcode中就计算超时了。
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) {

        // write your code here

        ArrayList<Integer> result = new  ArrayList<Integer>();

        if (A == null || A.length == 0) {

            return 0;

}

        result.add(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++) {

            curList.add(A[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;
    }

//打印所有方案版本

int[] res;

int tot;

int[] A;

int K;

int[][][] f;

void printAnswer(int i, int j, int k) {

if (j == 0) {

for (int h = 0; h < K; ++h) {

System.out.print(res[h]);

if (h == K - 1) {

System.out.println("=" + tot);

} else {

System.out.print("+");

}

return;

}

if (f[i - 1][j][k] > 0) {

printAnswer(i - 1, j, k);

}

if (j > 0 && k >= A[i - 1] && f[i - 1][j - 1][k - A[i - 1]] > 0) {

res[j - 1] = A[i - 1];

printAnswer(i - 1, j - 1, k - A[i - 1]);

}

public int kSum(int[] AA, int KK, int T) {

K = KK;

A = AA;

int n = A.length;

res = new int[K];

tot = T;

f = new int[n + 1][K + 1][T + 1];

int i, j, k;

for (j = 0; j <= K; ++j) {

for (k = 0; k <= T; ++k) {

f[0][j][k] = 0;

}

f[0][0][0] = 1;

for (i = 1; i <= n; ++i) {

for (j = 0; j <= K; ++j) {

for (k = 0; k <= T; ++k) {

// not using A[i - 1]

f[i][j][k] = f[i - 1][j][k];

// using A[i - 1]

if (j > 0 && k >= A[i - 1]) {

f[i][j][k] += f[i - 1][j - 1][k - A[i - 1]];

}

printAnswer(n, K, T);

return f[n][K][T];

}

另外，还有一些题目的变形，比如如果要求所有组合，满足
sum < k,
sum = k,
sum > k,
或者是 closest to k

Lintcode: K Sum I

Labels

Popular Posts