题目大意 给定一个整型数组，里面没有重复数字。求解所有可能的组合使得组合的和为给定的整数。
解题思路：使用dp(nums, target)表示所有的组合来得到目标值。那么对nums里的每一个num_i，dp(nums, target) = num_i X dp(nums, target - num_i)
所以可以使用记忆化递归的办法来求解。
1. 记忆化递归
class Solution(object):
def combinationSum4(self, nums, target):
self.f = [-1 for _ in range(target + 1)]
self.f[0] = 1
def dp(nums, target):
if target < 0:
return 0
if self.f[target] != -1:
return self.f[target]
ans = 0
for num in nums:
ans += dp(nums, target - num)
self.f[target] = ans
return ans
return dp(nums, target)
2. 递推/动态规划
class Solution(object):
def combinationSum4(self, nums, target):
f = [0 for _ in range(target + 1)]
f[0] = 1
for i in range(1, target + 1):
for num in nums:
if i - num >= 0:
f[i] += f[i - num]
return f[target]