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.

Have you met this question in a real interview? 

Yes

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上的原题，请参见我之前的博客 。

 

解法一：

class Solution {public:    /**     * @param nums an integer array and all positive numbers, no duplicates     * @param target an integer     * @return an integer     */    int backPackVI(vector
     
      & nums, int target) {        vector
      
        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
     
      & nums, int target) {        vector
      
        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();    }};