class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
}
};
剑指 Offer II 104. 排列的数目
给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3 输出：0
提示：
1 <= nums.length <= 2001 <= nums[i] <= 1000nums 中的所有元素 互不相同1 <= target <= 1000
进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
注意：本题与主站 377 题相同：https://leetcode.cn/problems/combination-sum-iv/
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-22 15:21:07
func combinationSum4(nums []int, target int) int {
dp := make([]int, target+1)
dp[0] = 1
for i := 1; i <= target; i++ {
for _, num := range nums {
if num <= i {
dp[i] += dp[i-num]
}
}
}
return dp[target]
}
python3 解法, 执行用时: 40 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-22 15:17:22
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [1] + [0] * target
for i in range(1, target + 1):
for num in nums:
if num <= i:
dp[i] += dp[i - num]
return dp[target]