If they’re equal, condition 2 would be satisfied. We can only use the current element if it is less than our target sum. Here, we use the current element - the additional element in the set of elements in our current row compared to the set of elements in the previous row - and check that we are able to attain the remainder of the target sum. If the above two conditions are not satisfied, we have one remaining way of attaining our target sum.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: We can always,trivially, arrive at a target sum of 0, regardless of the set of elements we have to work with.ĪDVERTISEMENT Step 4: Building the table (the crux of the problem) 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.
0 kommentar(er)
