k数和
2018-05-02 本文已影响1人
只为此心无垠
def kSum(self, A, k, target):
n = len(A)
if n <= 0 or k <= 0 or target <= 0:
return 0
# f[n][k][target]：表示当前和，把k和target都放入状态
# 表示前i个数字中找出j个数，使得这 j 个数的和等于 h 的方案数
# f(i, j, h) = f(i-1, j, h) + f(i-1, j-1, h-A[ i ])。
# （即取与不取第j个数的方案数之和，类似于01背包）
for i in range(n):
for j in range(k):
for h in range(target):
