Coding Patterns: 0/1 Knapsack (DP)

9 minute read

In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers and K-way Merge patterns and today, we will introduce 0/1 Knapsack pattern which is very useful to solve the famous Knapsack problem by using Dynamic Programming techniques.

We are going to use top-down Memoisation or bottom-up Tabulation technique to solve the problems efficiently.

Problem: Partition Equal Subset Sum

LeetCode 416 - Partition Equal Subset Sum [medium]

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Brute Force Solution

A basic brute-force solution could be to try all combinations of partitioning the given numbers into two sets to see if any pair of sets has an equal sum.

This essentially transforms our problem to: Find a subset of the given numbers that has a total sum of sum / 2.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        
        if s % 2 != 0:
            return False
        
        return self.can_partition_recursive(nums, s/2, 0)
    
    def can_partition_recursive(self, nums, sum, current_index):
        if sum == 0:
            return True
        
        if len(nums) == 0 or current_index >= len(nums):
            return False
        
        if nums[current_index] <= sum:
            if (self.can_partition_recursive(nums, sum - nums[current_index], current_index + 1)):
                return True
        
        return self.can_partition_recursive(nums, sum, current_index + 1)

Time Complexity: O(2N) where N represents the total number.

Space Complexity: O(N) which will be used to store recursion stack.

Top-down Dynamic Programming with Memoization

We can use memoization to overcome the overlapping sub-problems. Since we need to store the results for every subset and for every possible sum, therefore we will be using a two-dimensional array to store the results of the solved sub-problems.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        
        if s % 2 != 0:
            return False
        
        # initialize two-dimensional dp array, -1 for default
        dp = [[-1 for x in range(int(s/2)+1)] for y in range(len(nums))]
        
        if self.can_partition_recursive(dp, nums, int(s / 2), 0) == 1:
            return True  # return True for 1
        else:
            return False  # return False for 0
        
    def can_partition_recursive(self, dp, nums, sum, current_index):
        if sum == 0:
            return 1
        
        if len(nums) == 0 or current_index >= len(nums):
            return 0
        
        if dp[current_index][sum] == -1:  # if we have not processed this sub-problem
                if nums[current_index] <= sum:
                    if self.can_partition_recursive(dp, nums, sum - nums[current_index], current_index + 1) == 1:
                        dp[current_index][sum] = 1
                        return 1

                # recursive call after excluding the number at the current_index
                dp[current_index][sum] = self.can_partition_recursive(dp, nums, sum, current_index + 1)

        return dp[current_index][sum]

Time Complexity: O(N * S) where N represents the total numbers and S is the total sum of all numbers.

Space Complexity: O(N * S)

Bottom-up Dynamic Programming with Tabulation

Let’s try to populate our dp[][] array from the above solution by working in a bottom-up fashion with using tabulation dynamic programming technique.

Essentially, we want to find if we can make all possible sum with every subset. This means, dp[i][s] will be True if we can make the sum s from the first i numbers.

For each number at index i and sum s, we have these two options:

  1. Exclude the number. In this case, we will see if we can get s from the subset excluding this number: dp[i-1][s]
  2. Include the number if its value is not more than s. In this case, we will see if we can find a subset to get the remaining sum: dp[i-1][s-num[i]]
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        
        if s % 2 != 0:
            return False
        
        s = int(s / 2)
        dp = [[False for x in range(s + 1)] for y in range(len(nums))]
        
        # populate s = 0 columns
        for i in range(0, len(nums)):
            dp[i][0] = True
            
        # form a subset only when the required sum is equal to its value
        for j in range(1, s + 1):
            dp[0][j] = nums[0] == j
        
        # process all subsets for all sums
        for i in range(1, len(nums)):
            for j in range(1, s + 1):
                # if we can get the sum 'j' without the number at index 'i'
                if dp[i - 1][j]:
                    dp[i][j] = dp[i - 1][j]
                    
                # else if we can find a subset to get the remaining sum
                elif j >= nums[i]:
                    dp[i][j] = dp[i - 1][j - nums[i]]
        
        # the bottom-right corner will have our answer
        return dp[len(nums) - 1][s]

Time Complexity: O(N * S) where N represents the total numbers and S is the total sum of all numbers.

Space Complexity: O(N * S)

How to identify?

0/1 Knapsack pattern is very useful to solve the famous Knapsack problem by using Dynamic Programming techniques.

Knapsack problem is all about optimization. For example, given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

We are using top-down Memoisation or bottom-up Tabulation technique to solve these problems efficiently.

Similar LeetCode Problems