#239. 带约束的组合求和

    ID: 239 Type: Default 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>codingbatRecursion-2gesp6DFS递归

带约束的组合求和

组合求和与特殊约束

题目背景

聪聪最近在研究如何从一组数字中挑选出特定组合。他遇到一个有趣的问题,需要你帮助解决。

题目描述

给定一个整数数组 numsnums 和一个目标和 targettarget,判断是否可能从数组中选择一组整数,使得它们的和等于 targettarget,并满足以下附加约束:

  1. 数组中所有 55 的倍数都必须包含在所选的组中。
  2. 如果一个 55 的倍数紧跟着一个 11,那么这个 11 必须不能被选中。 (无需使用循环)

输入格式

输入包含一行。 这一行包含一个整数 start_indexstart\_index,一个用方括号包围的整数列表 numsnums,以及一个整数 targettarget。 在本题中,start_indexstart\_index 始终为 00

start_index [num1 num2 ... numK] target

输出格式

输出以如下格式输出到标准输出中。

如果存在符合条件的组合,输出 true;否则输出 false

样例

0 [2 5 10 4] 19
true
0 [2 5 10 4] 17
true
0 [2 5 10 4] 12
false

样例解释

样例 1: 对于输入 0 [2 5 10 4] 19,数组中的 55 的倍数是 551010,它们必须被包含。它们的和是 1515。目标和是 1919,还需要 44。从剩余的元素 2,42, 4 中选择 44 即可达到目标。最终选择的组为 5,10,45, 10, 4,和为 1919。因此输出 true

样例 2: 对于输入 0 [2 5 10 4] 17,数组中的 55 的倍数是 551010,它们必须被包含。它们的和是 1515。目标和是 1717,还需要 22。从剩余的元素 2,42, 4 中选择 22 即可达到目标。最终选择的组为 5,10,25, 10, 2,和为 1717。因此输出 true

样例 3: 对于输入 0 [2 5 10 4] 12,数组中的 55 的倍数是 551010,它们必须被包含。它们的和是 1515。由于 1515 已经大于目标和 1212,因此不可能通过添加非负数达到目标。因此输出 false

数据范围

每个测试用例的时间限制为 11 秒,内存限制为 10241024 KiB。