Computer scienceProgramming languagesJavaInterview preparationAlgorithms and problem solving techniques

Dynamic programming approach in action

Theory

Composing a sum

Report a typo

Write a method that accepts an integer as a target number and an array of positive integers and then returns true if the target number can be represented by a sum of any elements of the array, otherwise false. Any element of the array may be reused infinitely. A sum of elements may consist of a single element.

Consider a target number 17 and an array [12, 5, 17]. As you can see, the number 17 can be represented, for example, as a sum of 12 + 5 or as 17 so the method will return true.

In another example, a target number 27 cannot be represented as a sum of the elements of an array [5, 7, 18, 11], so the method will return false.

Hint: you may check if the target number can be a sum of elements by subtracting each element from the target number recursively. The recursion tree of the first example can be as follows:

The recursion tree

If at least one leaf in this tree is equal to 0, the target number can be represented as a sum of the elements.

Sample Input 1: 

74
9 17 15 2 16 8

Sample Output 1: 

TRUE

Sample Input 2: 

11
16 13 5 13 8 9

Sample Output 2: 

FALSE

Sample Input 3: 

62
5 12 14 8 11

Sample Output 3: 

TRUE
Write a program in Java 17
import java.util.Scanner;

class Sum {
public static boolean evaluate(int targetNumber, int[] array) {
// write your code here
return false;
}
}

// do not modify this code
class Main {
public static void main(String[] args) {
var scanner = new Scanner(System.in);
var targetNumber = scanner.nextInt();
var array = scanner.tokens().mapToInt(Integer::parseInt).toArray();
System.out.println(Sum.evaluate(targetNumber, array) ? "TRUE" : "FALSE");
}
}
___

Create a free account to access the full topic