Maximice el número de elementos de Array con suma como máximo K

Dada una array A[] de N enteros y un entero K ,  la tarea es seleccionar el número máximo de elementos de la array cuya suma sea como máximo K.

Ejemplos:

Entrada: A[] = {1, 12, 5, 111, 200, 1000, 10}, K = 50 
Salida: 4 
Explicación: 
El número máximo de selecciones será 1, 12, 5, 10, es decir, 1 + 12 + 5 + 10 = 28 < 50.

Entrada: A[] = {3, 7, 2, 9, 4}, K = 15 
Salida: 3 
Explicación: 
El número máximo de selecciones será 3, 2, 4, es decir, 3 + 2 + 4 = 9 < 15.

Enfoque ingenuo: la idea es generar todas las subsecuencias posibles de la array y encontrar la suma de elementos de todas las subsecuencias generadas. Encuentre la subsecuencia con longitud máxima y con la suma menor o igual a K . 
Tiempo Complejidad: O(2 ^N ) 
Espacio Auxiliar: (1)
 

Enfoque eficiente: el enfoque eficiente se puede resolver usando la técnica Greedy . A continuación se muestran los pasos:  

1. Ordenar la array dada.
2. Iterar en la array y realizar un seguimiento de la suma de elementos hasta que la suma sea menor o igual a K .
3. Si la suma durante la iteración en los pasos anteriores excede K , rompa el ciclo e imprima el valor de conteo hasta ese índice.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to select a maximum number of
// elements in array whose sum is at most K
int maxSelections(int A[], int n, int k)
{
    // Sort the array
    sort(A, A + n);
 
    // Calculate the sum and count while
    // iterating the sorted array
    int sum = 0;
    int count = 0;
 
    // Iterate for all the
    // elements in the array
    for (int i = 0; i < n; i++) {
 
        // Add the current element to sum
        sum = sum + A[i];
 
        if (sum > k) {
            break;
        }
 
        // Increment the count
        count++;
    }
    // Return the answer
    return count;
}
 
// Driver Code
int main()
{
    // Given array
    int A[] = { 3, 7, 2, 9, 4 };
 
    // Given sum k
    int k = 15;
    int n = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    cout << maxSelections(A, n, k);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to select a maximum number of
// elements in array whose sum is at most K
static int maxSelections(int A[], int n, int k)
{
     
    // Sort the array
    Arrays.sort(A);
 
    // Calculate the sum and count while
    // iterating the sorted array
    int sum = 0;
    int count = 0;
 
    // Iterate for all the
    // elements in the array
    for(int i = 0; i < n; i++)
    {
         
        // Add the current element to sum
        sum = sum + A[i];
 
        if (sum > k)
        {
            break;
        }
 
        // Increment the count
        count++;
    }
     
    // Return the answer
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array
    int A[] = { 3, 7, 2, 9, 4 };
 
    // Given sum k
    int k = 15;
    int n = A.length;
 
    // Function call
    System.out.print(maxSelections(A, n, k));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for
# the above approach
 
# Function to select a maximum
# number of elements in array
# whose sum is at most K
def maxSelections(A, n, k):
 
  # Sort the array
  A.sort();
   
  # Calculate the sum and
  # count while iterating
  # the sorted array
  sum = 0;
  count = 0;
 
  # Iterate for all the
  # elements in the array
  for i in range(n):
 
    # Add the current element to sum
    sum = sum + A[i];
 
    if (sum > k):
      break;
 
      # Increment the count
      count += 1;
 
      # Return the answer
      return count;
 
# Driver Code
if __name__ == '__main__':
 
  # Given array
  A = [3, 7, 2, 9, 4];
 
  # Given sum k
  k = 15;
  n = len(A);
 
  # Function call
  print(maxSelections(A, n, k));
     
# This code is contributed by gauravrajput1

// C# program for the above approach
using System;
 
class GFG{
 
// Function to select a maximum number of
// elements in array whose sum is at most K
static int maxSelections(int[] A, int n, int k)
{
 
    // Sort the array
    Array.Sort(A);
 
    // Calculate the sum and count while
    // iterating the sorted array
    int sum = 0;
    int count = 0;
 
    // Iterate for all the
    // elements in the array
    for(int i = 0; i < n; i++)
    {
         
        // Add the current element to sum
        sum = sum + A[i];
 
        if (sum > k)
        {
            break;
        }
 
        // Increment the count
        count++;
    }
 
    // Return the answer
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
 
    // Given array
    int[] A = { 3, 7, 2, 9, 4 };
 
    // Given sum k
    int k = 15;
    int n = A.Length;
 
    // Function call
    Console.Write(maxSelections(A, n, k));
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program for the above approach
 
// Function to select a maximum number of
// elements in array whose sum is at most K
function maxSelections( A, n, k)
{
    // Sort the array
    A.sort();
 
    // Calculate the sum and count while
    // iterating the sorted array
    let sum = 0;
    let count = 0;
 
    // Iterate for all the
    // elements in the array
    for (let i = 0; i < n; i++) {
 
        // Add the current element to sum
        sum = sum + A[i];
 
        if (sum > k) {
            break;
        }
 
        // Increment the count
        count++;
    }
    // Return the answer
    return count;
}
 
 
// Driver Code
 
// Given array
let A = [ 3, 7, 2, 9, 4 ];
 
// Given sum k
let k = 15;
let n = A.length;
 
// Function Call
document.write(maxSelections(A, n, k));
 
</script>

3

Complejidad de tiempo: O(N*log N) 
Espacio auxiliar: O(1)