🔗 Picking Two and Adding Them

You are given an integer array numbers. Complete the solution function to return, in ascending order in an array, all the numbers that can be made by picking two numbers at different indices in numbers and adding them together.

• The length of numbers is between 2 and 100.
  • Every number in numbers is between 0 and 100.

Example #1

• 2 = 1 + 1 (there are two 1's in numbers.)
• 3 = 2 + 1
• 4 = 1 + 3
• 5 = 1 + 4 = 2 + 3
• 6 = 2 + 4
• 7 = 3 + 4

So it must return { 2, 3, 4, 5, 6, 7 }.

Example #2

• 2 = 0 + 2
• 5 = 5 + 0
• 7 = 0 + 7 = 5 + 2
• 9 = 2 + 7
• 12 = 5 + 7

So it must return { 2, 5, 7, 9, 12 }.

This algorithm requires computing every possible sum obtained by picking any two integers from the integer array numbers and adding them together.

1. An algorithm for picking any two elements from the array
2. Storing the sum of the two numbers

For step 1, a nested for loop would work fine, but this time let's take a more algorithmic approach. Let's extract the elements using a combination algorithm based on backtracking.

For step 2, let's use a HashSet to keep only the unique sum values.

JAVA
/**
 * Combination method (backtracking)
 *
 * @param numbers: [int[]] target array
 * @param isCheck: [int[]] array tracking backtracking selection
 * @param start: [int] starting value
 * @param target: [int] number of elements to combine
 */
private void combination(int[] numbers, boolean[] isCheck, int start, int target)
{
	// When the number of elements to combine is 0 (search complete)
	if (target == 0)
	{
		int sum = 0;
		
		for (int i = 0; i < numbers.length; i++)
		{
			// If marked as selected during backtracking
			if (isCheck[i])
			{
				sum += numbers[i];
			}
		}
		
		set.add(sum);
	}
	
	// Otherwise
	else
	{
		for (int i = start; i < numbers.length; i++)
		{
			isCheck[i] = true;
			
			combination(numbers, isCheck, i + 1, target - 1);
			
			isCheck[i] = false;
		}
	}
}

The backtracking combination algorithm looks like the above.

After performing the combination, add the sum of the two selected values into the HashSet object.

Then sort the values and return them as an array.

JAVA
import java.util.HashSet;

/**
 * Picking Two and Adding Them class
 *
 * @author RWB
 * @since 2021.12.12 Sun 03:19:39
 */
class Solution
{
	private HashSet<Integer> set;
	
	/**
	 * Method that returns the answer
	 *
	 * @param numbers: [int[]] integer array
	 *
	 * @return [int[]] answer
	 */
	public int[] solution(int[] numbers)
	{
		set = new HashSet<>();
		
		boolean[] isCheck = new boolean[numbers.length];
		
		combination(numbers, isCheck, 0, 2);
		
		return set.stream().mapToInt(Integer::intValue).sorted().toArray();
	}
	
	/**
	 * Combination method (backtracking)
	 *
	 * @param numbers: [int[]] target array
	 * @param isCheck: [int[]] array tracking backtracking selection
	 * @param start: [int] starting value
	 * @param target: [int] number of elements to combine
	 */
	private void combination(int[] numbers, boolean[] isCheck, int start, int target)
	{
		// When the number of elements to combine is 0 (search complete)
		if (target == 0)
		{
			int sum = 0;
			
			for (int i = 0; i < numbers.length; i++)
			{
				// If marked as selected during backtracking
				if (isCheck[i])
				{
					sum += numbers[i];
				}
			}
			
			set.add(sum);
		}
		
		// Otherwise
		else
		{
			for (int i = start; i < numbers.length; i++)
			{
				isCheck[i] = true;
				
				combination(numbers, isCheck, i + 1, target - 1);
				
				isCheck[i] = false;
			}
		}
	}
}