Find all the pairs in a given unordered set of numbers whose sum is equal to a given input sum

This problem can be approached in different ways, such as like having nested loops which loop through each and every number of the set and perform a combination of sums and compare with the sum supplied. But we don’t want to use this, as it takes higher time complexity because of the nested loops.

Instead, we can address this problem in this way: we can take a single number from the array and see if we had already seen the other part of the sum for this current number which forms the expected sum. For example, if we pick up the number 2 from the array, if we know that we had already seen an 8 in the array (because 10-2 = 8) then we can say that 2,8 form a pair for the solution.

To keep a memory of the past numbers we have already seen, we can maintain a set of the "complements" for this given number. So for the above example, as soon as we pick up 2 and realize that 8 is needed for this to be called a pair, we place the 8 inside this "complements" set and on further looping we can check if the current number is already there in the "complements" set or not. If the current number from the array is 8 and now since 8 is already there in the "complements" set, we can say that there was a 2 that has come before and 2,8 is a pair from the solution.

Logic:

The solution is approached as below:

1. loop through the given array of numbers
2. maintain a set of complement numbers
3. check if the expectedSum – currentNumber exists
4. if the number exists, add the currentNumber, expectedSum – currentNumber as a pair to resultPairs
5. if the number doesn’t exist, add the expectedSum – currentNumber into the set

Code in C#:

        public void DoFindPairsForSum(int[] arrayOfNumbers, int expectedSum)
        {
            List<KeyValuePair<int, int>> expectedSumPairs 
              = new List<KeyValuePair<int, int>>();
            
            HashSet<int> complementSum = new HashSet<int>();

            for (int i = 0; i < arrayOfNumbers.Length; i++)
            {
                int complement = expectedSum - arrayOfNumbers[i];
                if (complementSum.Contains(arrayOfNumbers[i]))
                {
                    expectedSumPairs.Add(
                    new KeyValuePair<int, int>(arrayOfNumbers[i], complement));
                }
                else
                {
                    complementSum.Add(complement);
                }
            }

            foreach (var item in expectedSumPairs)
            {
                Console.WriteLine($"{item.Key},{item.Value}");
            }
        }

Note:

• Observe that we’ve taken a HashSet to place our complements instead of a List. Because HashSet offers a faster read access than a List.
• We’re using List<KeyValuePair<int,int>> instead of a Dictionary<int,int> although Dictionary<int,int> is internally a list of KeyValuePair. This is because having a List<KeyValuePair<int,int>> keeps things simple and faster than a Dictionary.

*This problem is based on the question used in Google Example Coding Interview Video