Coding Patterns: 0/1 Knapsack (DP)
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:
- Exclude the number. In this case, we will see if we can get
sfrom the subset excluding this number:dp[i-1][s] - 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.