Problem Find If Numbers In Array Sum To Total - RobAllan27/CodingProblems GitHub Wiki

Problem

This package aims to deal with the following problem

Given a set of numbers, can we see if for any two numbers in the list, if added they will match a total. Given a list of numbers and target number T, return true or false whether any two numbers from the list add up to T.

• So as an example, given [9, 14, 5, 7] and T = 16, return true since 9 + 7 is 16.
• Further, how can we optimise this into one pass?
• Further, rather than just 2 numbers, return true or false if there are N numbers. So if N was 3 in the above, and T was 21 then return true as 9 + 5 + 7 = 21.
• One can assume that N will be smaller that the size of the list.
• Test cases are included in the package.

Solution - Strategy overview

• Part 1 - simply see if we can make the total out of 2 entries
• Part 2 - simply see if we can make the total out of N entries

Strategy for part 1 - simply see if we can make the total out of 2 entries

• Create an set of Integers - as an array list because we want to delete
• We will iterate through the set of integers
• take the found integer value from the target total - leaves 'remainder'
• See if the remainder exists in the set of Integers - if so we return true
• if not we get rid of the first value form the array list and work on the shorter array list.
• Stop when the array list only has 1 entry left and return false..

Strategy for part 2 - simply see if we can make the total out of N entries

• get the String into a Arraylist ofIntegers
• then we work out a list of all the positions in the array - like 0,1,2, ... n
• then we fill the combinations of those position.
• then we take each of those combinations and see if for any of them we get the target.
• if any match we return positive