在 Python 中查找不能表示为给定数组的任何子集之和的最小正整数值

pythonserver side programmingprogramming更新于 2025/10/16 0:12:17

假设我们有一个正数的排序数组，该数组按升序排序，我们必须找到不能表示为给定集合的任何子集元素之和的最小正值。我们必须在 O(n) 时间内解决这个问题。

因此，如果输入为 A = [1, 4, 8, 12, 13, 17]，则输出将为 2。

要解决这个问题，我们将遵循以下步骤 −

n := A 的大小
answer := 1
对于范围为 0 到 n 的 i，执行
- 如果 A[i] <= answer，则
  - answer := answer + A[i]
- 否则，
  - 从循环
返回 answer

示例

让我们看看下面的实现以便更好地理解 −

def get_smallest_element(A):
   n = len(A)
   answer = 1
   for i in range (0, n ):
      if A[i] <= answer:
         answer = answer + A[i]
      else:
         break
   return answer
A = [1, 4, 8, 12, 13, 17]
print(get_smallest_element(A))