leetcode 链接：377. 组合总和 Ⅳ

题目

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。

示例：

  1. 输入：nums = [1,2,3], target = 4
  2. 输出：7
  3. 解释：
  4. 所有可能的组合为：
  5. (1, 1, 1, 1)
  6. (1, 1, 2)
  7. (1, 2, 1)
  8. (1, 3)
  9. (2, 1, 1)
  10. (2, 2)
  11. (3, 1)
  12. 请注意，顺序不同的序列被视作不同的组合。
输入：nums = [9], target = 3
输出：0

解答 & 代码

此题题目叫组合总和，实际上求的是排列数。
求排列数是完全背包问题的一种，外层循环 target，内层循环 nums 数组

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // 动态规划 dp 数组，dp[i] 代表和 i 的排列数
        vector<int> dp(target + 1, 0);
        dp[0] = 1;    // 初始化
        for(int i = 0; i <= target; ++i)            // 外层循环 target
        {
            for(int j = 0; j < nums.size(); ++j)    // 内层循环 nums 数组的元素
            {
                if(i - nums[j] >= 0 && dp[i - nums[j]] < INT_MAX - dp[i])
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6.5 MB, 在所有 C++ 提交中击败了 31.25% 的用户