Group Sum with No Consecutive Elements

Background

Congcong is playing a number game where he needs to select some numbers from a sequence, but with the restriction that no two adjacent numbers can be selected simultaneously.

Problem Description

Given an array of integers nums, determine if it's possible to choose a group of some of the integers such that their sum equals the given target target, with an additional constraint: If a value in the array is chosen to be in the group, the value immediately following it in the array must not be chosen. This problem is typically solved recursively, without explicit loops.

Input Format

Input is given from standard input in the following format.

start nums target

Where start is an integer representing the starting index for consideration (usually $0$); nums is an array of integers; and target is an integer representing the target sum.

Output Format

Output is printed to standard output in the following format.

result

result is a boolean value, true if such a group exists, false otherwise.

Sample

0 [2 5 10 4] 12

true

0 [2 5 10 4] 14

false

0 [2 5 10 4] 7

false

Sample Explanation

Sample 1: For input 0 [2 5 10 4] 12, we can choose 2 and 10. Their sum is $2 + 10 = 12$. 2 is chosen, 5 (following 2) is not chosen; 10 is chosen, 4 (following 10) is not chosen. The constraint is satisfied, so the output is true.

Sample 2: For input 0 [2 5 10 4] 14, no combination summing to $14$ can be found under the given constraint, so the output is false.

Sample 3: For input 0 [2 5 10 4] 7, no combination summing to $7$ can be found under the given constraint, so the output is false.

Constraints

Time limit for each test case is $1$ second, and memory limit is $1024$ MiB.