377.组合总和IV

发表于： 分类于：
字数： 560 阅读：≈ 2分钟

😄377.组合总和IV

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

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

思路

基本思想

选取几个整数组成一个target，相当于找出恰好装满背包的方案数，并且整数可以重复选择，所以是完全背包的组合问题，得到的递推方程为： $$ dp[j]+=d[j-nums[i]] $$ 其中dp[j]代表组成目标整数j的方案数，本问题是一个排列问题，因为(1, 1, 2)，(1, 2, 1)，(2, 1, 1)是三个不一样的情况，所以需要先遍历背包容量，再遍历物品

最后返回dp[target]即可

执行流程

  1. 初始化dp数组，注意dp[0]=1
  2. 按照完全背包的流程进行统计
  3. 返回dp[target]作为最终的答案

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution
{
public:
    int combinationSum4(vector<int> &nums, int target)
    {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int j = 0; j <= target; ++j)//先遍历背包容量
        {
            for (int i = 0; i < nums.size(); ++i)//在遍历物品
            {
                //可以装下物品并且方案数没有超过int的范围
                if (j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]])
                {
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
};

总结

主要有以下几点需要注意：

  • 排列问题需要先遍历背包容量
  • 求方案数需要累加
  • 需要判断背包是否能装下，否则dp[j-nums[i]]中的j-nums[i]可能会是负数
  • 要判断方案数是否还在int类型的范围内