Dado un entero S y un arreglo arr[] , la tarea es encontrar el número mínimo de elementos cuya suma sea S, de modo que cualquier elemento del arreglo pueda elegirse cualquier número de veces para obtener la suma S.
Ejemplos:
Entrada: arr[] = {25, 10, 5}, S = 30
Salida: 2
Explicación:
En la array dada hay muchas soluciones posibles como –
5 + 5 + 5 + 5 + 5 + 5 = 30, o
10 + 10 + 10 = 30, o
25 + 5 = 30
Por lo tanto, la solución mínima posible es 2Entrada: arr[] = {2, 1, 4, 3, 5, 6}, Sum= 6
Salida: 1
Explicación:
En la array dada hay muchas soluciones posibles como –
2 + 2 + 2 = 6, o
2 + 4 = 6, o
6 = 6,
por lo tanto, la solución mínima posible es 1
Enfoque:
La idea es encontrar todas las sucesiones posibles recursivamente de modo que su suma sea igual a la S dada y también realizar un seguimiento de la secuencia mínima de modo que su suma sea S. De esta manera, la solución mínima posible se puede calcular fácilmente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum number of sequence
// required from array such that
// their sum is equal to given S
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// minimum elements required to
// get the sum of given value S
int printAllSubsetsRec(int arr[],
int n,
vector<int> v,
int sum)
{
// Condition if the
// sequence is found
if (sum == 0) {
return (int)v.size();
}
if (sum < 0)
return INT_MAX;
// Condition when no
// such sequence found
if (n == 0)
return INT_MAX;
// Calling for without choosing
// the current index value
int x = printAllSubsetsRec(
arr,
n - 1, v, sum);
// Calling for after choosing
// the current index value
v.push_back(arr[n - 1]);
int y = printAllSubsetsRec(
arr, n, v,
sum - arr[n - 1]);
return min(x, y);
}
// Function for every array
int printAllSubsets(int arr[],
int n, int sum)
{
vector<int> v;
return printAllSubsetsRec(arr, n,
v, sum);
}
// Driver Code
int main()
{
int arr[] = { 2, 1, 4, 3, 5, 6 };
int sum = 6;
int n = sizeof(arr) / sizeof(arr[0]);
cout << printAllSubsets(arr, n, sum)
<< endl;
return 0;
}
Java
// Java implementation to find the
// minimum number of sequence
// required from array such that
// their sum is equal to given S
import java.util.*;
import java.lang.*;
class GFG{
// Function to find the
// minimum elements required to
// get the sum of given value S
static int printAllSubsetsRec(int arr[],
int n,
ArrayList<Integer> v,
int sum)
{
// Condition if the
// sequence is found
if (sum == 0)
{
return (int)v.size();
}
if (sum < 0)
return Integer.MAX_VALUE;
// Condition when no
// such sequence found
if (n == 0)
return Integer.MAX_VALUE;
// Calling for without choosing
// the current index value
int x = printAllSubsetsRec(
arr,
n - 1, v, sum);
// Calling for after choosing
// the current index value
v.add(arr[n - 1]);
int y = printAllSubsetsRec(
arr, n, v,
sum - arr[n - 1]);
v.remove(v.size() - 1);
return Math.min(x, y);
}
// Function for every array
static int printAllSubsets(int arr[],
int n, int sum)
{
ArrayList<Integer> v = new ArrayList<>();
return printAllSubsetsRec(arr, n,
v, sum);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 1, 4, 3, 5, 6 };
int sum = 6;
int n = arr.length;
System.out.println(printAllSubsets(arr, n, sum));
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation to find the # minimum number of sequence # required from array such that # their sum is equal to given S import sys # Function to find the # minimum elements required to # get the sum of given value S def printAllSubsetsRec(arr, n, v, Sum): # Condition if the # sequence is found if (Sum == 0): return len(v) if (Sum < 0): return sys.maxsize # Condition when no # such sequence found if (n == 0): return sys.maxsize # Calling for without choosing # the current index value x = printAllSubsetsRec(arr, n - 1, v, Sum) # Calling for after choosing # the current index value v.append(arr[n - 1]) y = printAllSubsetsRec(arr, n, v, Sum - arr[n - 1]) v.pop(len(v) - 1) return min(x, y) # Function for every array def printAllSubsets(arr, n, Sum): v = [] return printAllSubsetsRec(arr, n, v, Sum) # Driver code arr = [ 2, 1, 4, 3, 5, 6 ] Sum = 6 n = len(arr) print(printAllSubsets(arr, n, Sum)) # This code is contributed by avanitrachhadiya2155
C#
// C# implementation to find the
// minimum number of sequence
// required from array such that
// their sum is equal to given S
using System;
using System.Collections.Generic;
class GFG{
// Function to find the
// minimum elements required to
// get the sum of given value S
static int printAllSubsetsRec(int[] arr, int n,
List<int> v, int sum)
{
// Condition if the
// sequence is found
if (sum == 0)
{
return v.Count;
}
if (sum < 0)
return Int32.MaxValue;
// Condition when no
// such sequence found
if (n == 0)
return Int32.MaxValue;
// Calling for without choosing
// the current index value
int x = printAllSubsetsRec(arr, n - 1,
v, sum);
// Calling for after choosing
// the current index value
v.Add(arr[n - 1]);
int y = printAllSubsetsRec(arr, n, v,
sum - arr[n - 1]);
v.RemoveAt(v.Count - 1);
return Math.Min(x, y);
}
// Function for every array
static int printAllSubsets(int[] arr, int n,
int sum)
{
List<int> v = new List<int>();
return printAllSubsetsRec(arr, n, v, sum);
}
// Driver code
static void Main()
{
int[] arr = { 2, 1, 4, 3, 5, 6 };
int sum = 6;
int n = arr.Length;
Console.WriteLine(printAllSubsets(arr, n, sum));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript implementation to find the
// minimum number of sequence
// required from array such that
// their sum is equal to given S
// Function to find the
// minimum elements required to
// get the sum of given value S
function prletAllSubsetsRec(arr, n, v,
sum)
{
// Condition if the
// sequence is found
if (sum == 0)
{
return v.length;
}
if (sum < 0)
return Number.MAX_VALUE;
// Condition when no
// such sequence found
if (n == 0)
return Number.MAX_VALUE;
// Calling for without choosing
// the current index value
let x = prletAllSubsetsRec(
arr,
n - 1, v, sum);
// Calling for after choosing
// the current index value
v.push(arr[n - 1]);
let y = prletAllSubsetsRec(
arr, n, v,
sum - arr[n - 1]);
v.pop(v.length - 1);
return Math.min(x, y);
}
// Function for every array
function prletAllSubsets(arr,
n, sum)
{
let v = [];
return prletAllSubsetsRec(arr, n,
v, sum);
}
// Driver Code
let arr = [ 2, 1, 4, 3, 5, 6 ];
let sum = 6;
let n = arr.length;
document.write(prletAllSubsets(arr, n, sum));
</script>
Producción:
1
Análisis de rendimiento:
- Complejidad de tiempo: como en el enfoque anterior, hay dos opciones para cada número en cada paso que toma el tiempo O (2 N ), por lo tanto, la complejidad del tiempo será O (2 N ) .
- Complejidad espacial: como en el enfoque anterior, no se utiliza espacio adicional, por lo que la complejidad espacial será O(1) .
Enfoque eficiente: como en el enfoque anterior, hay subproblemas superpuestos, por lo que la idea es utilizar el paradigma de programación dinámica para resolver este problema. Cree una tabla DP de N * S para almacenar la respuesta precalculada para la secuencia anterior, que es la secuencia de longitud mínima requerida para obtener la suma como S – arr[i] y, de esta manera, finalmente después de calcular para cada valor de la array, la respuesta al problema será dp[N][S], donde m es la longitud de la array y S es la suma dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum number of sequence
// required from array such that
// their sum is equal to given S
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of
// minimum length of the sequence
int Count(int S[], int m, int n)
{
vector<vector<int> > table(
m + 1,
vector<int>(
n + 1, 0));
// Loop to initialize the array
// as infinite in the row 0
for (int i = 1; i <= n; i++) {
table[0][i] = INT_MAX - 1;
}
// Loop to find the solution
// by pre-computation for the
// sequence
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (S[i - 1] > j) {
table[i][j]
= table[i - 1][j];
}
else {
// Minimum possible
// for the previous
// minimum value
// of the sequence
table[i][j]
= min(
table[i - 1][j],
table[i][j - S[i - 1]] + 1);
}
}
}
return table[m][n];
}
// Driver Code
int main()
{
int arr[] = { 9, 6, 5, 1 };
int m = sizeof(arr) / sizeof(arr[0]);
cout << Count(arr, m, 11);
return 0;
}
Java
// Java implementation to find the
// minimum number of sequence
// required from array such that
// their sum is equal to given S
import java.util.*;
class GFG{
// Function to find the count of
// minimum length of the sequence
static int Count(int S[], int m, int n)
{
int [][]table = new int[m + 1][n + 1];
// Loop to initialize the array
// as infinite in the row 0
for(int i = 1; i <= n; i++)
{
table[0][i] = Integer.MAX_VALUE - 1;
}
// Loop to find the solution
// by pre-computation for the
// sequence
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if (S[i - 1] > j)
{
table[i][j] = table[i - 1][j];
}
else
{
// Minimum possible for the
// previous minimum value
// of the sequence
table[i][j] = Math.min(table[i - 1][j],
table[i][j - S[i - 1]] + 1);
}
}
}
return table[m][n];
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 9, 6, 5, 1 };
int m = arr.length;
System.out.print(Count(arr, m, 11));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 implementation to find the # minimum number of sequence # required from array such that # their sum is equal to given S # Function to find the count of # minimum length of the sequence def Count(S, m, n): table = [[0 for i in range(n + 1)] for i in range(m + 1)] # Loop to initialize the array # as infinite in the row 0 for i in range(1, n + 1): table[0][i] = 10**9 - 1 # Loop to find the solution # by pre-computation for the # sequence for i in range(1, m + 1): for j in range(1, n + 1): if (S[i - 1] > j): table[i][j] = table[i - 1][j] else: # Minimum possible # for the previous # minimum value # of the sequence table[i][j] = min(table[i - 1][j], table[i][j - S[i - 1]] + 1) return table[m][n] # Driver Code if __name__ == '__main__': arr= [9, 6, 5, 1] m = len(arr) print(Count(arr, m, 11)) # This code is contributed by Mohit Kumar
C#
// C# implementation to find the
// minimum number of sequence
// required from array such that
// their sum is equal to given S
using System;
class GFG{
// Function to find the count of
// minimum length of the sequence
static int Count(int[] S, int m, int n)
{
int[,] table = new int[m + 1, n + 1];
// Loop to initialize the array
// as infinite in the row 0
for(int i = 1; i <= n; i++)
{
table[0, i] = int.MaxValue - 1;
}
// Loop to find the solution
// by pre-computation for the
// sequence
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if (S[i - 1] > j)
{
table[i, j] = table[i - 1, j];
}
else
{
// Minimum possible for the
// previous minimum value
// of the sequence
table[i, j] = Math.Min(table[i - 1, j],
table[i, j - S[i - 1]] + 1);
}
}
}
return table[m, n];
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 9, 6, 5, 1 };
int m = 4;
Console.WriteLine(Count(arr, m, 11));
}
}
// This code is contributed by jrishabh99
Javascript
<script>
// JavaScript implementation to find the
// minimum number of sequence
// required from array such that
// their sum is equal to given S
// Function to find the count of
// minimum length of the sequence
function Count(S, m, n)
{
let table = [];
for(let i = 0;i<m+1;i++){
table[i] = [];
for(let j = 0;j<n+1;j++){
table[i][j] = 0;
}
}
// Loop to initialize the array
// as infinite in the row 0
for (let i = 1; i <= n; i++) {
table[0][i] = Number.MAX_VALUE - 1;
}
// Loop to find the solution
// by pre-computation for the
// sequence
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (S[i - 1] > j) {
table[i][j]
= table[i - 1][j];
}
else {
// Minimum possible
// for the previous
// minimum value
// of the sequence
table[i][j]
= Math.min(
table[i - 1][j],
table[i][j - S[i - 1]] + 1);
}
}
}
return table[m][n];
}
// Driver Code
let arr = [ 9, 6, 5, 1 ];
let m = arr.length;
document.write(Count(arr, m, 11));
</script>
Producción:
2
Análisis de rendimiento:
- Complejidad de tiempo: como en el enfoque anterior, hay dos bucles para el cálculo de la secuencia de longitud mínima requerida que requiere un tiempo O(N 2 ), por lo que la complejidad de tiempo será O(N 2 ) .
- Complejidad espacial: como en el enfoque anterior, se utiliza una tabla dp adicional, por lo que la complejidad espacial será O(N 2 ) .