Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm


Given a list of unique positive integers nums and a positive integer k, return the number of unique combinations that sum up to k. You may reuse numbers when creating combinations.

Constraints
n ≤ 25 where n is the length of nums
1 ≤ nums[i] ≤ 250 for all 0 ≤ i < n
1 ≤ k ≤ 500
Example 1
Input
nums = [1, 2, 3]
k = 2
Output
2
Explanation
We can make 2 with [1, 1] and [2].

Backtracking Algorithm to Count Multiset Sum (Knapsack Problem)

This is one of the Knapsack problem. We can solve this using Dynamic Programming Algorithm. Alternatively we can perform backtracking algorithm when the given input dataset is small.

Given N unique items with each weight given – we want to pack the knapsack (total capacity is k). We can recursively backtracking picking the item until we either fill up the knapsack or the total items chosen exceed capacity k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int countMultisetSum(vector<int>& nums, int k) {
    int ans = 0;
    function<void(int, int)> dfs = [&](int idx, int k) {
        if (k == 0) {
            ans ++;
        }
        if (k < 0) {
            return;
        }
        if (idx == nums.size()) {
            return;
        }
        for (int i = idx; i < nums.size(); ++ i) {
            dfs(i, k - nums[i]);
        }
    };
    dfs(0, k);
    return ans;
}
int countMultisetSum(vector<int>& nums, int k) {
    int ans = 0;
    function<void(int, int)> dfs = [&](int idx, int k) {
        if (k == 0) {
            ans ++;
        }
        if (k < 0) {
            return;
        }
        if (idx == nums.size()) {
            return;
        }
        for (int i = idx; i < nums.size(); ++ i) {
            dfs(i, k - nums[i]);
        }
    };
    dfs(0, k);
    return ans;
}

However, this may be inefficient, as for each item, we can take or not take – which results in time complexity O(2^N) – as we are simulating the process of packing each item in the knapsack.

A more efficient algorithm to solve this knapsack problem is via Bottom-up Dynamic Programming Algorithm: Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm

Knapsack Problems

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
373 words
Last Post: Teaching Kids Programming - Breadth First Search Algorithm to Check the Completeness of a Binary Tree
Next Post: Teaching Kids Programming - Longest Consecutive Run of 1s in Binary

The Permanent URL is: Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm

Leave a Reply