Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Notice
The different sequences are counted as different combinations.
Example
Given nums = [1, 2, 4], target = 4
The possible combination ways are:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
return 6
不太懂这题名称为啥叫backpack，LeetCode上的原题，请参见我之前的博客Combination Sum IV 。
解法一：
class Solution { public: /** * @param nums an integer array and all positive numbers, no duplicates * @param target an integer * @return an integer */ int backPackVI(vector<int>& nums, int target) { vector<int> dp(target + 1, 0); dp[0] = 1; for (int i = 1; i <= target; ++i) { for (auto a : nums) { if (a <= i) { dp[i] += dp[i - a]; } } } return dp.back(); } };
解法二：
class Solution { public: /** * @param nums an integer array and all positive numbers, no duplicates * @param target an integer * @return an integer */ int backPackVI(vector<int>& nums, int target) { vector<int> dp(target + 1, 0); dp[0] = 1; sort(nums.begin(), nums.end()); for (int i = 1; i <= target; ++i) { for (auto a : nums) { if (a > i) break; dp[i] += dp[i - a]; } } return dp.back(); } };
本文转自博客园Grandyang的博客，原文链接：背包之六[LintCode] Backpack VI ，如需转载请自行联系原博主。
![每日一题---27. 移除元素[力扣][Go]](https://ucc.alicdn.com/images/user-upload-01/37bfee28c43e42efb785309a4ceb94fa.png?x-oss-process=image/resize,h_160,m_lfit)
![每日一题---1005. K 次取反后最大化的数组和[力扣][Go]](https://ucc.alicdn.com/images/user-upload-01/563d2be270bc4f49a517098938de37cc.png?x-oss-process=image/resize,h_160,m_lfit)
![每日一题---1034. 边界着色[力扣][Go]](https://ucc.alicdn.com/images/user-upload-01/ed6477c681bf495e81f8bbb86acc170b.png?x-oss-process=image/resize,h_160,m_lfit)
![每日一题---748. 最短补全词[力扣][Go]](https://ucc.alicdn.com/images/user-upload-01/7bf0bd74603d40dd9a12968120825b11.png?x-oss-process=image/resize,h_160,m_lfit)
![每日一题---1380. 矩阵中的幸运数[力扣][Go]](https://ucc.alicdn.com/images/user-upload-01/2a2b2d43f4884d5393a7cc0558129951.png?x-oss-process=image/resize,h_160,m_lfit)