Subset Sum with Recursion

Background

This problem explores a fundamental recursive backtracking technique. Understanding this pattern is crucial for solving many problems that involve searching through a space of choices.

Problem Description

Given an array of integers, determine if it's possible to choose a group of some of these integers such that their sum equals a given target. This is a classic backtracking recursion problem. Once you grasp the recursive backtracking strategy here, you can apply the same pattern to many problems involving searching a choice space. Instead of examining the entire array, our convention is to consider the portion of the array starting at index start and continuing to the end. The caller can specify the entire array by simply passing start as $0$. No loops are needed; the recursive calls traverse the array.

Input Format

Input is given from standard input in the following format.

start [array_elements] target

Output Format

Output is printed to standard output in the following format.

true or false

Sample

0 [2 4 8] 10

true

0 [2 4 8] 14

true

0 [2 4 8] 9

false

Sample Explanation

For the first sample, choosing $2$ and $8$ from the array [2 4 8] sums to $10$, which matches the target. For the second sample, choosing $2$, $4$, and $8$ from the array [2 4 8] sums to $14$, which matches the target. For the third sample, no combination of numbers from [2 4 8] sums to $9$.

Constraints

Time limit: 1s, Memory limit: 1024KiB for each test case.