🔗 Target Number

There are n non-negative integers. You want to add or subtract these numbers appropriately to make a target number. For example, to make the number 3 using [1, 1, 1, 1, 1], you can use the following five methods.

• -1+1+1+1+1 = 3
• +1-1+1+1+1 = 3
• +1+1-1+1+1 = 3
• +1+1+1-1+1 = 3
• +1+1+1+1-1 = 3

Given an array numbers containing the numbers to use, and a target number target as parameters, write a solution function that returns the number of ways to make the target number by appropriately adding and subtracting the numbers.

• The number of given numbers is between 2 and 20, inclusive.
• Each number is a natural number between 1 and 50, inclusive.
• The target number is a natural number between 1 and 1000, inclusive.

Same as the example given in the problem.

We need to find the number of ways to add and subtract the elements of numbers appropriately so that the result becomes target.

Using a DFS algorithm, we add and subtract each number in numbers to compute a sum, and compare it against target, counting whenever they match.

JAVA
/**
 * Target Number class
 *
 * @author RWB
 * @since 2021.12.28 Tue 12:31:46
 */
class Solution
{
	/**
	 * Answer return method
	 *
	 * @param numbers: [int[]] Integer array
	 * @param target: [int] Target number
	 *
	 * @return [int] Answer
	 */
	public int solution(int[] numbers, int target)
	{
		return dfs(numbers, 0, 0, target);
	}
	
	/**
	 * DFS algorithm result return method
	 *
	 * @param numbers: [int[]] Integer array
	 * @param depth: [int] Depth
	 * @param sum: [int] Sum
	 * @param target: [int] Target number
	 *
	 * @return [int] Result
	 */
	public int dfs(int[] numbers, int depth, int sum, int target)
	{
		// If we've fully traversed
		if (depth == numbers.length)
		{
			// If the target number and sum are equal
			if (target == sum)
			{
				return 1;
			}
			
			// If not
			else
			{
				return 0;
			}
		}
		
		// If not
		else
		{
			return dfs(numbers, depth + 1, sum + numbers[depth], target) + dfs(numbers, depth + 1, sum - numbers[depth], target);
		}
	}
}