#239. 带约束的组合求和
带约束的组合求和
组合求和与特殊约束
题目背景
聪聪最近在研究如何从一组数字中挑选出特定组合。他遇到一个有趣的问题,需要你帮助解决。
题目描述
给定一个整数数组 和一个目标和 ,判断是否可能从数组中选择一组整数,使得它们的和等于 ,并满足以下附加约束:
- 数组中所有 的倍数都必须包含在所选的组中。
- 如果一个 的倍数紧跟着一个 ,那么这个 必须不能被选中。 (无需使用循环)
输入格式
输入包含一行。 这一行包含一个整数 ,一个用方括号包围的整数列表 ,以及一个整数 。 在本题中, 始终为 。
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,数组中的 的倍数是 和 ,它们必须被包含。它们的和是 。目标和是 ,还需要 。从剩余的元素 中选择 即可达到目标。最终选择的组为 ,和为 。因此输出 true。
样例 2: 对于输入 0 [2 5 10 4] 17,数组中的 的倍数是 和 ,它们必须被包含。它们的和是 。目标和是 ,还需要 。从剩余的元素 中选择 即可达到目标。最终选择的组为 ,和为 。因此输出 true。
样例 3: 对于输入 0 [2 5 10 4] 12,数组中的 的倍数是 和 ,它们必须被包含。它们的和是 。由于 已经大于目标和 ,因此不可能通过添加非负数达到目标。因此输出 false。
数据范围
每个测试用例的时间限制为 秒,内存限制为 KiB。