LeetCode377. 组合总和 Ⅳ

题目

分析

本题要结合LeetCode518.零钱兑换II这道题一起看，零钱兑换是组合个数总和，而本题排列个数总和，也就是说 (1, 2, 1) 和 (2, 1, 1)是不同的。遍历顺序：要先遍历背包容量再遍历物品。正好与组合问题遍历顺序相反，组合问题不允许重复，所以要先遍历物品再遍历背包容量。由于完全背包问题，在遍历背包容量时用正序遍历。

注意：本题对C++有坑，会出现和大于int情形

代码

 1 class Solution {
 2 public:
 3     int combinationSum4(vector<int>& nums, int target) {
 4         vector<int>dp(target+1,0);
 5         dp[0] = 1;
 6         //先遍历容量再遍历物品
 7         for(int j = 0;j <= target;j++){
 8             for(int i = 0;i < nums.size();i++){
 9                 if(j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]) 
10                     dp[j] += dp[j-nums[i]];
11             }
12         }
13         return dp[target];
14     }
15 };

总结

对于两个数超INT的情形的处理， dp[j] < INT_MAX - dp[j - nums[i]]——参考代码随想录Carl