Problem

You are given an array of non-negative integers and a target number. Your task is to find how many ways you can add and subtract the given numbers to achieve the target number. The order of numbers in the array must be preserved. For example, with the array [1, 1, 1, 1, 1], there are five ways to reach the target number 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
• +1 + 1 + 1 + 1 - 1 = 3

Implement the function solution which, given an array numbers and a target number target, returns the number of different ways to add or subtract the numbers to equal the target.

Constraints

• The number of integers in the array is between 2 and 20.
• Each number is a natural number between 1 and 50.
• The target number is a natural number between 1 and 1000.

Example

Explanation of Examples

• Example 1:
  • As described in the problem statement, there are five ways to combine the operations of addition and subtraction to achieve the target number 3 using the array [1, 1, 1, 1, 1].
• Example 2:
  • There are two ways to achieve the target number 4 with the array [4, 1, 2, 1]:
    • +4 + 1 - 2 + 1 = 4
    • +4 - 1 + 2 - 1 = 4

How to Approach?

Step1: Initialize variables in loop

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }

    private int dfs(int[] numbers, int target, int index, int sum) {
        if (index == numbers.length) {
            if (sum == target) {
                return 1; 
            }
            return 0; 
        }

        int plus = dfs(numbers, target, index + 1, sum + numbers[index]);
        int minus = dfs(numbers, target, index + 1, sum - numbers[index]);

        return plus + minus;
    }
}