Encuentre el valor entero positivo más pequeño que no se puede representar como la suma de cualquier subconjunto de una array dada

Dada una array de números positivos, encuentre el valor entero positivo más pequeño que no se puede representar como la suma de elementos de cualquier subconjunto de un conjunto dado. 
La complejidad de tiempo esperada es O(nlogn).

Ejemplos: 

Input:  arr[] = {1, 10, 3, 11, 6, 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

Una solución simple es comenzar desde el valor 1 y verificar todos los valores uno por uno si pueden sumar valores en la array dada. Esta solución es muy ineficiente ya que se reduce al problema de la suma de subconjuntos , que es un conocido problema NP-Completo .

Usando un bucle simple, podemos resolver este problema en tiempo O (N log N). Deje que la array de entrada sea arr[0..n-1]. Primero ordenamos la array en orden no decreciente. Deje que el elemento más pequeño que no puede ser representado por elementos en los índices de 0 a (i-1) sea ‘res’. Inicializamos ‘res’ como 1 (la respuesta más pequeña posible) y recorremos la array dada desde i=0. Existen las siguientes dos posibilidades cuando consideramos el elemento en el índice i:

1. Decidimos que ‘res’ es el resultado final : si arr[i] es mayor que ‘res’, encontramos la brecha que es ‘res’ porque los elementos después de arr[i] también serán mayores que ‘res ‘.
2. El valor de ‘res’ se incrementa después de considerar arr[i] : si arr[i] no es mayor que ‘res’, el valor de ‘res’ se incrementa en arr[i], por lo que ‘res’ = ‘res’+ arr[i] (¿por qué? Si los elementos de 0 a (i-1) pueden 

representan 1 a ‘res-1’, entonces los elementos de 0 a i pueden representar de 1 a ‘res + arr[i] – 1’ agregando arr[i] a todos los subconjuntos que representan 1 a ‘res-1’ que ya han determinado ser representados)
A continuación se presenta la implementación de la idea anterior. 

// C++ program to find the smallest positive value that cannot be
// represented as sum of subsets of a given sorted array
#include<iostream>
#include<vector>
#include<algorithm>
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]
long long smallestpositive(vector<long long> arr, int n) {
   long long int res = 1; // Initialize result
  
   sort(arr.begin(), arr.end());
   // 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() {
   vector<long long> arr1 = {1, 3, 4, 5};
   cout << smallestpositive(arr1, arr1.size()) << endl;
  
   vector<long long> arr2 = {1, 2, 6, 10, 11, 15};
   cout << smallestpositive(arr2, arr2.size()) << endl;
  
   vector<long long> arr3 = {1, 1, 1, 1};
   cout << smallestpositive(arr3, arr3.size()) << endl;
  
   vector<long long> arr4 = {1, 1, 3, 4};
   cout << smallestpositive(arr4, arr4.size()) << endl;
  
   return 0;
 }

// Java program to find the smallest positive value that cannot be
// represented as sum of subsets of a given sorted array
import java.util.Arrays;
 
class FindSmallestInteger
{
    // 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
 
          // sort the input array
          Arrays.sort(arr);
       
        // Traverse the array and increment 'res' if arr[i] is
        // smaller than or equal to 'res'.
        for (int i = 0; i < n; i++)
        {
          if(arr[i] > res){
            return res;
           }
          else{
            res+=arr[i];
          }
        }
             
        return res;
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        FindSmallestInteger small = new FindSmallestInteger();
        int arr1[] = {1, 3, 4, 5};
        int n1 = arr1.length;
        System.out.println(small.findSmallest(arr1, n1));
 
        int arr2[] = {1, 2, 6, 10, 11, 15};
        int n2 = arr2.length;
        System.out.println(small.findSmallest(arr2, n2));
 
        int arr3[] = {1, 1, 1, 1};
        int n3 = arr3.length;
        System.out.println(small.findSmallest(arr3, n3));
 
        int arr4[] = {1, 1, 3, 4};
        int n4 = arr4.length;
        System.out.println(small.findSmallest(arr4, n4));
 
    }
}
 
// This code has been contributed by Mukul Sharma (msharma04)

# Python3 program to find the smallest
# positive value that cannot be
# represented as sum of subsets
# of a given sorted array
 
# Returns the smallest number
# that cannot be represented as sum
# of subset of elements from set
# represented by sorted array arr[0..n-1]
def findSmallest(arr, n):
 
    res = 1 #Initialize result
 
    # Traverse the array and increment
    # 'res' if arr[i] is smaller than
    # or equal to 'res'.
    for i in range (0, n ):
        if arr[i] <= res:
            res = res + arr[i]
        else:
            break
    return res
 
 
# Driver program to test above function
arr1 = [1, 3, 4, 5]
n1 = len(arr1)
print(findSmallest(arr1, n1))
 
arr2= [1, 2, 6, 10, 11, 15]
n2 = len(arr2)
print(findSmallest(arr2, n2))
 
arr3= [1, 1, 1, 1]
n3 = len(arr3)
print(findSmallest(arr3, n3))
 
arr4 = [1, 1, 3, 4]
n4 = len(arr4)
print(findSmallest(arr4, n4))
 
# This code is.contributed by Smitha Dinesh Semwal

// C# program to find the smallest
// positive value that cannot be
// represented as sum of subsets
// of a given sorted array
using System;
 
class GFG {
     
    // Returns the smallest number that
    // cannot be represented as sum
    // of subset of elements from set
    // represented by sorted array
    // arr[0..n-1]
    static int findSmallest(int []arr, int n)
    {
         // Initialize result
         int res = 1;
 
        // 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 code
    public static void Main()
    {
        int []arr1 = {1, 3, 4, 5};
        int n1 = arr1.Length;
        Console.WriteLine(findSmallest(arr1, n1));
 
        int []arr2 = {1, 2, 6, 10, 11, 15};
        int n2 = arr2.Length;
        Console.WriteLine(findSmallest(arr2, n2));
 
        int []arr3 = {1, 1, 1, 1};
        int n3 = arr3.Length;
        Console.WriteLine(findSmallest(arr3, n3));
 
        int []arr4 = {1, 1, 3, 4};
        int n4 = arr4.Length;
        Console.WriteLine(findSmallest(arr4, n4));
 
    }
}
 
// This code is contributed by Sam007

<?php
// PHP program to find the smallest
// positive value that cannot be
// represented as sum of subsets
// of a given sorted array
 
// Returns the smallest number that
// cannot be represented as sum of
// subset of elements from set
// represented by sorted array
// arr[0..n-1]
function findSmallest($arr, $n)
{
     
    // Initialize result
    $res = 1;
     
    // Traverse the array and
    // increment 'res' if arr[i] is
    // smaller than or equal to 'res'.
    for($i = 0; $i < $n and $arr[$i] <= $res; $i++)
        $res = $res + $arr[$i];
     
    return $res;
}
 
// Driver Code
$arr1 = array(1, 3, 4, 5);
$n1 = count($arr1);
echo findSmallest($arr1, $n1),"\n";
 
$arr2 = array(1, 2, 6, 10, 11, 15);
$n2 = count($arr2);
echo findSmallest($arr2, $n2),"\n" ;
 
$arr3 = array(1, 1, 1, 1);
$n3 = count($arr3);
echo findSmallest($arr3, $n3),"\n";
 
$arr4 = array(1, 1, 3, 4);
$n4 = count($arr4);
echo findSmallest($arr4, $n4);
 
// This code is contributed by anuj_67.
?>

<script>
// javascript program to find the smallest positive value that cannot be
// represented as sum of subsets of a given sorted array
 
    // Returns the smallest number that cannot be represented as sum
    // of subset of elements from set represented by sorted array arr[0..n-1]
    function findSmallest(arr , n)
    {
        var res = 1; // Initialize result
 
        // Traverse the array and increment 'res' if arr[i] is
        // smaller than or equal to 'res'.
        for (i = 0; i < n && arr[i] <= res; i++)
            res = res + arr[i];
 
        return res;
    }
 
    // Driver program to test above functions
 
        var arr1 = [ 1, 3, 4, 5 ];
        var n1 = arr1.length;
        document.write(findSmallest(arr1, n1)+"<br/>");
 
        var arr2 = [ 1, 2, 6, 10, 11, 15 ];
        var n2 = arr2.length;
        document.write(findSmallest(arr2, n2)+"<br/>");
 
        var arr3 = [ 1, 1, 1, 1 ];
        var n3 = arr3.length;
        document.write(findSmallest(arr3, n3)+"<br/>");
 
        var arr4 = [ 1, 1, 3, 4 ];
        var n4 = arr4.length;
        document.write(findSmallest(arr4, n4)+"<br/>");
 
// This code is contributed by aashish1995
</script>

2
4
5
10

La Complejidad de Tiempo del programa anterior es O(nlogn). 

La Complejidad espacial es O (1) en el mejor de los casos para la ordenación en montón.