模版题-动态规划-组合总和IV( 完全背包-排列 )
- 版权声明：本站原创文章，于2026-05-19，由 管理员 发表。
- 转载请注明： 模版题-动态规划-组合总和IV( 完全背包-排列 ) | CodeGarden
```python
class Solution:
# 一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
# 请从 nums 中找出并返回总和为 target 的元素组合的个数。
def combinationSum4(self, nums: List[int], target: int) -> int:
# 和 '零钱兑换II' 几乎一样
# 区别在于 '零钱兑换II', 而本题求排列
dp = [ 0 for _ in range( target + 1 ) ]
dp[ 0 ] = 1
# 排列循环顺序很重要:先背包再物品
# 1. 若先物品再背包:物品i只能出现在物品i+1前,而没有排列的效果
# 2. 若先背包再物品:物品i可以出现在任意位置之前或之后,有排列的效果
for i in range( 1, target + 1 ):
for v in nums:
# 容量为i的背包,装入nums内的物品
if i - v >= 0: dp[ i ] = dp[ i ] + dp[ i - v ]
return dp[ target ]
```