# 查找不能表示为给定数组的任何子集之和的最小正整数值 > 原文： [https://www.geeksforgeeks.org/find-smallest-value-represented-sum-subset-given-array/](https://www.geeksforgeeks.org/find-smallest-value-represented-sum-subset-given-array/) 给定一个带正数的排序数组（以非降序排列），找到不能表示为给定集合的任何子集的元素之和的最小正整数值。 预期时间复杂度为`O(n)`。 例子： ``` Input: arr[] = {1, 3, 6, 10, 11, 15}; Output: 2 Input: arr[] = {1, 1, 1, 1}; Output: 5 Input: arr[] = {1, 1, 3, 4}; Output: 10 Input: arr[] = {1, 2, 5, 10, 20, 40}; Output: 4 Input: arr[] = {1, 2, 3, 4, 5, 6}; Output: 22 ``` **简单解决方案**是从值 1 开始，并逐一检查所有值是否可以求和到给定数组中的值。 该解决方案效率很低，因为它简化为[子集和问题](https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/)，这是众所周知的 [NP 完全问题](https://www.geeksforgeeks.org/np-completeness-set-1/)。 我们可以使用一个简单的循环在`O(n)`时间中解决此问题**。 令输入数组为 arr [0..n-1]。 我们将结果初始化为 1（最小可能的结果）并遍历给定的数组。 让无法用索引 0 到（i-1）的元素表示的最小元素为“ res”，当我们考虑索引 i 的元素时，有以下两种可能性**： ***1）我们认为'res'是最终结果*** ：如果 arr [i]大于'res'，则我们发现差距为'res'，因为元素 在 arr [i]之后也将大于'res'。 ***2）考虑了 arr [i]之后，'res'的值增加*** ：'res'的值增加 arr [i]（为什么？如果元素从 0 到 （i-1）可以表示 1 到'res-1'，然后从 0 到 i 的元素可以表示从 1 到'res + arr [i] – 1'将'arr [i]'加到表示 1 的所有子集中 去'res'） 以下是上述想法的实现。 ## C++ ```cpp // C++ program to find the smallest positive value that cannot be // represented as sum of subsets of a given sorted array #include <bits/stdc++.h> using namespace std; // Returns the smallest number that cannot be represented as sum // of subset of elements from set represented by sorted array arr[0..n-1] int findSmallest(int arr[], int n) {    int res = 1; // Initialize result    // Traverse the array and increment 'res' if arr[i] is    // smaller than or equal to 'res'.    for (int i = 0; i < n && arr[i] <= res; i++)        res = res + arr[i];    return res; } // Driver program to test above function int main() {    int arr1[] = {1, 3, 4, 5};    int n1 = sizeof(arr1)/sizeof(arr1[0]);    cout << findSmallest(arr1, n1) << endl;    int arr2[] = {1, 2, 6, 10, 11, 15};    int n2 = sizeof(arr2)/sizeof(arr2[0]);    cout << findSmallest(arr2, n2) << endl;    int arr3[] = {1, 1, 1, 1};    int n3 = sizeof(arr3)/sizeof(arr3[0]);    cout << findSmallest(arr3, n3) << endl;    int arr4[] = {1, 1, 3, 4};    int n4 = sizeof(arr4)/sizeof(arr4[0]);    cout << findSmallest(arr4, n4) << endl;    return 0; } ```