[LintCode] Backpack VI 背包之六-白红宇

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();    }};

本文转自博客园Grandyang的博客，原文链接：，如需转载请自行联系原博主。