Constrained Subset Sum

Background

Congcong is solving an interesting number puzzle. He is given a set of integers and a target sum, and needs to select some numbers from this set such that their sum equals the target sum. However, this puzzle has a special rule that makes Congcong a bit confused.

Problem Description

Given an array of integers nums and a target integer target, determine if it's possible to choose a group of some of the integers from nums such that the group sums to the given target. Additionally, there is an extra constraint: if there are numbers in the array that are adjacent and have identical values, they must either all be chosen, or none of them chosen. For example, with the array [1, 2, 2, 2, 5, 2], the three 2's in the middle must either all be chosen or not, all as a group. (One loop can be used to find the extent of the identical values.)

Input Format

The input is given from standard input in the following format. It starts with an integer start (typically 0, indicating to process from the starting index of the array, but in this problem, it might just be a placeholder or used for the starting index of recursion), followed by an array of integers nums, and finally an integer target.

start [num1 num2 ... numN] target

Output Format

Output true if such a subset exists; otherwise, output false.

boolean

Sample

0 [2 4 8] 10

true

0 [1 2 4 8 1] 14

true

0 [2 4 4 8] 14

false

Sample Explanation

• Sample 1: Array [2, 4, 8], target sum 10. Choosing 2 and 8 gives a sum of 10. The condition is met, output true.
• Sample 2: Array [1, 2, 4, 8, 1], target sum 14. Choosing 2, 4, and 8 gives a sum of 14. The condition is met, output true.
• Sample 3: Array [2, 4, 4, 8], target sum 14.
  • If the two 4s are chosen, the current sum is 8. We need 14 - 8 = 6. It's not possible to get 6 from the remaining [2, 8].
  • If the two 4s are not chosen, the current sum is 0. We need 14. It's not possible to get 14 from the remaining [2, 8] (only 2, 8, 10 are possible sums).
  • Therefore, no such subset can be found, output false.

Constraints

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