Lintcode 564: Backpack VI

https://www.lintcode.com/problem/combination-sum-iv/description

Notes:

As indicated by the title of the question, this problem belongs to backpack or knapsack problems.

But this question does not ask how many ways to fill up the bag, instead, it asks how many combinations to fill up the bag.

Or another way to say this,  the order of picking up one elements does matter!!!

Let say dp[v] represents the ways of combinations to fill it up.

Then,

dp[v] = sum {dp[v - val[i]]}, when v >= val[i].

The meaning is straightforward: we just add another val[i] element at the end of all the previous results. And each of them will still be a unique combination, so it still can be counted as one solution.

The key is that: we must put the first loop as the volume increasing from 1 to v; the inner loop is the elements. This is different from the typical knapsack problem, which is just the opposite.

So what is the difference?

The different is that: if we put the elements in the outside loop, then the order of elements inside the solution does not matter. Or we are calculating how many way to fill up the bag.

This question asks for how may combinations, so we need to pay attention to the relative orders of the elements.

See the code below:

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) {
        // write your code here
        vector<int> dp(target+1, 0);
        dp[0] = 1; //must have
        for(int i=1; i<=target; ++i) {
            for(int j=0; j<nums.size(); ++j) {
                if(i >= nums[j]) dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};

To better understand the subtle difference discussed above, we can run a small example: [1, 2], and target = 3.

To this question, the answer is 3. [1, 1, 1], [1, 2], and [2, 1].

If we ask for how many ways to fill-up the bag ignoring the relative orders. then it is 2. [1, 1, 1], and [1, 2].