# 查找不能表示為給定數組的任何子集之和的最小正整數值 > 原文： [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; } ```