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

• Teaching Kids Programming - 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming)
• Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm
• Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
• Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm
• Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
• Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
• Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm
• Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm
• Complete Knapsack Problem
• 0/1 Knapsack Problem
• Teaching Kids Programming - Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
• Algorithms Series: 0/1 BackPack - Dynamic Programming and BackTracking
• Using BackTracking Algorithm to Find the Combination Integer Sum
• Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
• Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP

–EOF (The Ultimate Computing & Technology Blog) —