K sum

Two sum 作为一个入门题，之后有3sum，4sum这样的，逐步升级为k sum. 两种问题，一种是求所有解，一种是求解的个数。前者就是backtracking，后者dp。下面来讨论下这两种题的解法。 Given n unique integers, number k (1<=k<=n) and target. Find all possible k integers where their sum is target. 这个暴力解法是O(C(N, K))就是n个数中取k个，求和看是否满足，满足就加入结果集，类似combination sum那道题。这个时间复杂度是O(min(n^k, n^(n-k)))。目前所知的最优解是O(N^(k-1)).
这里有个人的blog写的很详细了，我觉得我就不用再抄一遍了。ksum总结
第二种dp问题，看了一下答案，抱歉，完全不明白，三维dp，真的是超出了我的能力范围。把代码贴上，有兴趣的请自行观瞻。

public int  kSum(int A[], int k, int target) {
    int n = A.length;
    int[][][] f = new int[n + 1][k + 1][target + 1];
    for (int i = 0; i < n + 1; i++) {
        f[i][0][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k && j <= i; j++) {
            for (int t = 1; t <= target; t++) {
                f[i][j][t] = 0;
                if (t >= A[i - 1]) {
                    f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
                }
                f[i][j][t] += f[i - 1][j][t];
            } // for t
        } // for j
    } // for i
    return f[n][k][target];
}