今天看了一道谷歌K数之和的算法题，忽然想起来之前在力扣上做过2、3、4数之和的题，觉得很有必要来整理一下。
其实2、3、4数之和是一类题，用多个指针即可完成；K数之和是一类题，又是我学的最不好的DP。
假设数组为A，要找的分别是a、b、c、d，目标为target
2数之和：固定aPoint。bPoint去找target-A[aPoint];
3数之和：固定aPoint。bPoint和cPoint组成一个二数之和的问题，target=target-A[aPoint]；
4数之和：固定aPoint，bPoint。cPoint，dPoint组成一个二数之和的问题。
K数之和：设状态为f[i][j][p]，表示前i个数中找出j个数且和等于p的方案数目。
这个问题的关键在于到底要不要当前这个数A[i]。
也就是说，若要满足当前目标currentTarget，一共有两条路：
currentTarget的方案数=不要A[i]的方案数+要A[i]的方案数（当然A[i]要比当前目标值小，才能要）
public class Solution {
public int kSum(int[] A, int k, int target) {
if(A == null || A.length ==0 || k <= 0)
return 0;
//正整数的总数从0 - A.length； 可选的个数从 0 - k; target也是从 0 - target
int[][][] f = new int[A.length + 1][ k + 1][target + 1];
//初始值,
for(int i = 0; i <= A.length; i ++){
f[i][0][0] = 1;
}
//f[i][j][t] = f[i - 1][j][t] + f[i - 1][j - 1][t -A[i]]
for(int i = 1; i <= A.length; i ++)
for(int j = 1; j <= k; j ++)
for(int t = 1; t <= target; t ++){
//先更新当前的这个选项，还没有把第i个数选择进来
f[i][j][t] = f[i - 1][j][t];
//如果想把第i个数选进来，就要看第i个数是否大于目前的目标值
f[i][j][t] += t - A[i - 1] >=0 ? f[i - 1][j - 1][t -A[i - 1]] : 0;
}
return f[A.length][k][target];
}
}
