递推入门，LeetCode 377. 组合总和 Ⅳ

一、题目

1、题目描述

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

2、接口描述

python3

​

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:

cpp

​

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {

    }
};

 

3、原题链接

377. 组合总和 Ⅳ

---

 

二、解题报告

1、思路分析

看成一维坐标轴，你在起点0

每次可以选择往右跳num[i]步

问到达终点的方案数

f[ j ] = Σf[j - num[i]]

其实跟爬楼梯差不多

2、复杂度

时间复杂度： O(n)空间复杂度：O(n)

 

3、代码详解

python3

​

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = [1] + [0] * target
        for i in range(target + 1):
            for x in nums:
                if i >= x:
                    f[i] = (f[i] + f[i - x])
        return f[target]

cpp

​

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned> f(target + 1);
        f[0] = 1;
        for(int i = 1; i <= target; i++)
            for(int x : nums)
                if(i >= x)
                    f[i] += f[i - x];
        return f[target];
    }
};