# algorithms – Two-Sum Design – Pre-sort, Range Allowance, Many Sums

I would love feedback on the pseudocode design objectives outlined below.

• Pre-Sort: Optimize a two-sum solution that has a pre-sorted input.
• Range Allowance: Find a two-sum solution within a range plus/minus the given capacity.
• Many Sums: Convert a two-sum item solution to have as many items as possible based on a given capacity.

Two-Sum: Determine whether there are two items whose length will equal the total length while ensuring the same item cannot be used twice. This optimizes for runtime over memory.

• Time complexity: $$O(n)$$
• Space complexity: $$O(n)$$

## Samples

Input: `(4, 5, 2, 6)`

• Total length: `10`
• Expect: `true`

Input: `(4, 5, 2, 5)`

• Total length: `10`
• Expect: `true`

Input: `(4, 5, 2, 7)`

• Total length: `10`
• Expect: `false`

## Code

``````fun isLengthMatch(totalLength: Int, lengths: IntArray): Boolean {
handleErrors(totalLength, lengths)
val searchSet = hashSetOf<Int>()
for (length in lengths) {
val targetLength = totalLength - length
if (searchSet.contains(targetLength)) return true
}
return false
}

fun handleErrors(totalLength: Int, lengths: IntArray) {
if (totalLength <= 0) throw IllegalArgumentException(""totalLength" must be greater than 0.")
if (lengths.size < 2) throw IllegalArgumentException(""lengths" cannot be less than two items.")
}
``````

## Pre-Sort

1. Save a new var `lastTargetLength`
2. If the current `length` < `lastTargetLength`, there are no possible two-sums and return `false`.

i.e.

Input: `(6,2,1,0)`

Iterations

1. `targetLength = 9 - 6`, `lastTargetLength` = 3
2. Return false because the `length` of `2` < `lastTargetLength` of `3`.

## Range Allowance

1. Generate a `targetLengthsArray` +/- the `totalLength` and the given range allowance.

2. Check if the `searchSet` contains any of the values in the `targetLengthsArray`.

## Many Sums

Find the items that will produce the optimum sum with the given capacity.

1. Create a 2D array
• Rows: Items, ascending in capacity
• Columns: Capacity, ascending to max capacity
2. For each item, find the max value based on the capacity
• a. If the item capacity > current capacity: Choose the previous capacity value.
• b. Else: Choose the max of i and ii.
• i. Item value + Item value at (current capacity – item capacity)
• ii. Previous capacity value
• iii. If i == ii: Choose the previous item value.
3. Find the max value items.
• a. Check previous item at the same capacity until capacity == 0
• i. If current value == previous capacity value: Add the previous capacity value.
• ii. Else: Add the current item and look at the last item at (current capacity – item capacity).

See: 0/1 Knapsack Problem Dynamic Programming by Tushar Roy – Coding Made Simple