![]() ![]() The current element is exactly the sum we want to attain.Therefore, if we are able to attain a particular sum with a subset of the elements that we have presently, we can also attain that sum with our current set of elements - by simply not using the extra elements. the entry at row i-1 and column j is true. ![]() Some entry in the table at row i and column j is true (attainable) if one of the following three conditions are satisfied: Step 4: Building the table (the crux of the problem) We can always,trivially, arrive at a target sum of 0, regardless of the set of elements we have to work with. In the first column, every entry must be true. Naturally, we are unable to arrive at any target sum - column number - except 0. Recall that the first row represents an empty set. In the first row, every entry - except the first - must be false. We can immediately begin filling the entries for the base cases in our table - row 0 and column 0. So we only need to create totalSum / 2 + 1 columns, inclusive of 0. We only want to know if we can sum up exactly to half the total sum of the array. In total, we create n + 1 rows, inclusive of 0. Therefore, row 1 represents the first array element (index 0), row 2 represents the first two array elements (indices 0–1), and so on. The reason for this offset of 1 is because row 0 represents an empty set of elements. Table values are simply boolean values, indicating whether a sum (column) can be arrived at with a set of array elements (row).Ĭoncretely, row i represents a set of array elements from indices 0 to ( i-1). Table rows represent the set of array elements to be considered, while table columns indicate the sum we want to arrive at. We only proceed if the array adds up to an even sum. Trivially, if all the numbers in the array add up to an odd sum, we can return false. We will house our solution in a method that returns a boolean - true if the array can be partitioned into equal subsets, and false otherwise. Since this is a variation of KP, the logic and methodology is largely similar. Like with KP, we’ll be solving this using dynamic programming. This is the problem statement (reproduced partially without examples): 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.įor the full problem statement, with constraints and examples, check out the Leetcode problem. I first saw this problem on Leetcode - this was what prompted me to learn about, and write about, KP. Today I want to discuss a variation of KP: the partition equal subset sum problem. Previously, I wrote about solving the Knapsack Problem (KP) with dynamic programming. ![]()
0 Comments
Leave a Reply. |