k Sum

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?

http://www.lintcode.com/en/problem/k-sum/

Discussion

一组数取K个，满足和为某个值，就是Combination Sum问题的变形，只是要求path 的size是k的时候才输出。三十秒给出DFS版本。

Solution 1 - DFS

class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    int kSum(vector<int> A, int k, int target) {
        int cnt =  0;
        if(A.empty() || A.size() < k) return 0;
        sort(A.begin(), A.end());
        vector<int> path;
        dfs(A, k, target, path, 0, cnt);
        return cnt;
    }
    void dfs(vector<int> &nums, int k, int gap, vector<int> &path, int pos, int &cnt) {
        if(path.size() == k) {
            if(gap ==0) {
                cnt++;
            }
            return;
        }
        int n = nums.size();
        for(int i=pos; i<n; i++) {
            if(nums[i] > gap) {//prunning
                break;
            }
            path.emplace_back(nums[i]);
            dfs(nums, k, gap-nums[i], path, i+1, cnt);
            path.pop_back();
        }
    }
};

因为只是求个数，没有必要传递path，那怎么记录当前是否到了K个数字呢？k每次减一，到0的时候就可以了啊！

class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    int kSum(vector<int> A, int k, int target) {
        int cnt = 0;
        dfs(A, target, k, 0, cnt);
        return cnt;
    }
    void dfs(vector<int> &A, int gap, int k, int start, int &cnt) {
        if(k == 0 ) {
            if(gap == 0) {
                cnt++;
            }
            return;
        }
        for(int i= start; i<=A.size() - k; i++) {
            if(gap - A[i] < 0) {
                break;
            }
            dfs(A, gap - A[i], k-1, i+1, cnt);
        }
    }
};

Follow up

上面求组合的算法时间复杂度是O(C(n, k))，提交的时候不出意外的超时了。怎么剪枝都不行。。。

动归的思路：题目要求前n个数取k个组成和为target有多少种可能，把这句话generalize就是——前i个数取j个和为t的方案有多少？那动归的状态就有了：

• state: f[i][j][t] 前i个数取j个和为t的方案数
• function: f[i][j][t] = f[i-1][j][t] + f[i-1][j-1][t-A[i-1]]
  //前i-1个中取j个（不取最新的第i个，也就是A[i-1]），或者前i-1个取j-1个再加上A[i-1]
• 初始化：前i个中取0个和为0的方案数总是1

Solution 2 DP1

// Time:  O(k * n * t)
// Space: O(k * n * t)
class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    int kSum(vector<int> A, int k, int target) {
        if(A.empty() || A.size() < k) return 0;
        int n = A.size();
        vector<vector<vector<int> > > table(n+1, vector<vector<int> >(k+1, vector<int> (target+1, 0)));
        //tavle[i][j][t]: select j numbers from previous i numbers in A, sum to t, how may ways to do this.
        //init: select 0 from previous i numbers, target is t, 1 way only.
        for(int i=0; i<=n; i++) {
            table[i][0][0] = 1;
        }
        //state transformation:
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=k; j++) { //select k numbers at most;
                for(int t=1; t<=target; t++) {
                    table[i][j][t] = table[i-1][j][t]; //DON'T SELECT A[i-1]
                    if(t-A[i-1] <= target && t-A[i-1] >=0)
                        table[i][j][t] += table[i-1][j-1][t-A[i-1]]; //select A[i-1]
                }
            }
        }
        return table[n][k][target];
    }
};

Solution 3 DP2 saving space

状态的变化只跟上一行有关系，自然想到用两行的table就可以了。

// Time:  O(k * n * t)
// Space: O(n * t)
class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    int kSum(vector<int> A, int k, int target) {
        if(A.empty() || A.size() < k) return 0;
        int n = A.size();
        vector<vector<vector<int> > > table(2, vector<vector<int> >(k+1, vector<int> (target+1, 0)));
        //tavle[i][j][t]: select j numbers from previous i numbers in A, sum to t, how may ways to do this.
        //init: select 0 from previous i numbers, target is t, 1 way only.
        for(int i=0; i<=1; i++) {
            table[i][0][0] = 1;
        }
        //state transformation:
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=k; j++) { //select k numbers at most;
                for(int t=1; t<=target; t++) {
                    table[i%2][j][t] = table[(i-1)%2][j][t]; //DON'T SELECT A[i-1]
                    if(t-A[i-1] <= target && t-A[i-1] >=0)
                        table[i%2][j][t] += table[(i-1)%2][j-1][t-A[i-1]]; //select A[i-1]
                }
            }
        }
        return table[n%2][k][target];
    }
};

Follow up

j最多取到k，但是当i小于k的时候j最多取到i，把状态转移那里for(int j=1; j<=k; j++)改成for(int j=1; j<=min(i,k); j++)可以节省一半的时间。

Solution 4. DP3: savding space and time

从状态转移方程f[i][j][t] = f[i-1][j][t] + f[i-1][j-1][t-A[i-1]]可以看出来，自底向上要不上面的TOP-DOWN更节省时间，而且用一个二维表就可以了。

class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    int kSum(vector<int> A, int k, int target) {
        if(A.empty() || A.size() < k) return 0;
        int n = A.size();
        vector<vector<int> >  table(k+1, vector<int> (target+1, 0));
        //tavle[i][j][t]: select j numbers from previous i numbers in A, sum to t, how may ways to do this.
        //init: select 0 from previous i numbers, target is t, 1 way only.
         table[0][0] = 1;
        //state transformation:
        for(int i=1; i<=n; i++) {
            for(int j=min(i,k); j>=1; j--) { //select k numbers at most;
                for(int t=target; t>=A[i-1]; t--) {//注意这里t的下界
                        table[j][t] += table[j-1][t-A[i-1]]; //select A[i-1]
                }
            }
        }
        return table[k][target];
    }
};