组合总和IV
回溯法（超时）
class Solution { public: int result = 0; void backtracking(vector<int>& nums , int target , int sum) { if(sum == target) result++; if(sum >= target) return; for(int i=0 ;i<nums.size() ;i++) { backtracking(nums,target,sum+nums[i]); } return; } int combinationSum4(vector<int>& nums, int target) { backtracking(nums,target,0); return result; } };
动态规划
和518零钱兑换II 的区别是
- 518零钱兑换II 是组合数，有多少种组合
- 此题是找排序数
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
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++) { if(j>=nums[i] && dp[j] < INT_MAX - dp[j-nums[i]]) { dp[j] += dp[j-nums[i]]; } else dp[j] = dp[j]; } } return dp[target]; } };
C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。
二刷
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
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++) { if(j>=nums[i] && dp[j] <= INT_MAX - dp[j-nums[i]]) dp[j] += dp[j-nums[i]]; } } return dp[target]; } };
