Dado un arreglo de enteros arr[] de tamaño N y un entero X , la tarea es contar el número de subsecuencias en ese arreglo tal que su suma sea menor o igual a X .
Nota: 1 <= N <= 1000 y 1 <= X <= 1000, donde N es el tamaño de la array.
Ejemplos:
Entrada: arr[] = {84, 87, 73}, X = 100
Salida: 3
Explicación: Las tres subsecuencias con suma menor o igual a 100 son {84}, {87} y {73}.Entrada: arr[] = {25, 13, 40}, X = 50
Salida: 4
Explicación: Las cuatro subsecuencias con suma menor o igual a 50 son {25}, {13}, {40} y {25, 13 }.
Enfoque ingenuo: genere todas las subsecuencias de la array y verifique si la suma es menor o igual a X.
Complejidad de tiempo: O (2 N )
Enfoque Eficiente: Genere el conteo de subsecuencias usando Programación Dinámica . Para resolver el problema, siga los pasos a continuación:
- Para cualquier índice ind , si arr[ind] ≤ X entonces, el recuento de subsecuencias que incluyen y excluyen el elemento en el índice actual:
contarSubsecuencia(ind, X) = contarSubsecuencia(ind + 1, X) (excluyendo) + contarSubsecuencia(ind + 1, X – arr[ind]) (incluido)
- De lo contrario, cuente las subsecuencias excluyendo el índice actual:
contarSubsecuencia(ind, X) = contarSubsecuencia(ind + 1, X) (excluyendo)
- Finalmente, reste 1 del recuento final devuelto por la función, ya que también cuenta una subsecuencia vacía.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to count number
// of subsequences in an array
// with sum less than or equal to X
#include <bits/stdc++.h>
using namespace std;
// Utility function to return the count
// of subsequence in an array with sum
// less than or equal to X
int countSubsequenceUtil(
int ind, int sum,
int* A, int N,
vector<vector<int> >& dp)
{
// Base condition
if (ind == N)
return 1;
// Return if the sub-problem
// is already calculated
if (dp[ind][sum] != -1)
return dp[ind][sum];
// Check if the current element is
// less than or equal to sum
if (A[ind] <= sum) {
// Count subsequences excluding
// the current element
dp[ind][sum]
= countSubsequenceUtil(
ind + 1,
sum, A, N, dp)
+
// Count subsequences including
// the current element
countSubsequenceUtil(
ind + 1,
sum - A[ind],
A, N, dp);
}
else {
// Exclude current element
dp[ind][sum]
= countSubsequenceUtil(
ind + 1,
sum, A,
N, dp);
}
// Return the result
return dp[ind][sum];
}
// Function to return the count of subsequence
// in an array with sum less than or equal to X
int countSubsequence(int* A, int N, int X)
{
// Initialize a DP array
vector<vector<int> > dp(
N,
vector<int>(X + 1, -1));
// Return the result
return countSubsequenceUtil(0, X, A,
N, dp)
- 1;
}
// Driver Code
int main()
{
int arr[] = { 25, 13, 40 }, X = 50;
int N = sizeof(arr) / sizeof(arr[0]);
cout << countSubsequence(arr, N, X);
return 0;
}
Java
// Java program to count number
// of subsequences in an array
// with sum less than or equal to X
class GFG{
// Utility function to return the count
// of subsequence in an array with sum
// less than or equal to X
static int countSubsequenceUtil(int ind, int sum,
int []A, int N,
int [][]dp)
{
// Base condition
if (ind == N)
return 1;
// Return if the sub-problem
// is already calculated
if (dp[ind][sum] != -1)
return dp[ind][sum];
// Check if the current element is
// less than or equal to sum
if (A[ind] <= sum)
{
// Count subsequences excluding
// the current element
dp[ind][sum] = countSubsequenceUtil(
ind + 1, sum,
A, N, dp) +
// Count subsequences
// including the current
// element
countSubsequenceUtil(
ind + 1,
sum - A[ind],
A, N, dp);
}
else
{
// Exclude current element
dp[ind][sum] = countSubsequenceUtil(
ind + 1, sum,
A, N, dp);
}
// Return the result
return dp[ind][sum];
}
// Function to return the count of subsequence
// in an array with sum less than or equal to X
static int countSubsequence(int[] A, int N, int X)
{
// Initialize a DP array
int [][]dp = new int[N][X + 1];
for(int i = 0; i < N; i++)
{
for(int j = 0; j < X + 1; j++)
{
dp[i][j] = -1;
}
}
// Return the result
return countSubsequenceUtil(0, X, A,
N, dp) - 1;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 25, 13, 40 }, X = 50;
int N = arr.length;
System.out.print(countSubsequence(arr, N, X));
}
}
// This code is contributed by Rajput-Ji
C#
// C# program to count number
// of subsequences in an array
// with sum less than or equal to X
using System;
class GFG{
// Utility function to return the count
// of subsequence in an array with sum
// less than or equal to X
static int countSubsequenceUtil(int ind, int sum,
int []A, int N,
int [,]dp)
{
// Base condition
if (ind == N)
return 1;
// Return if the sub-problem
// is already calculated
if (dp[ind, sum] != -1)
return dp[ind, sum];
// Check if the current element is
// less than or equal to sum
if (A[ind] <= sum)
{
// Count subsequences excluding
// the current element
dp[ind, sum] = countSubsequenceUtil(
ind + 1, sum,
A, N, dp) +
// Count subsequences
// including the current
// element
countSubsequenceUtil(
ind + 1,
sum - A[ind],
A, N, dp);
}
else
{
// Exclude current element
dp[ind, sum] = countSubsequenceUtil(
ind + 1, sum,
A, N, dp);
}
// Return the result
return dp[ind, sum];
}
// Function to return the count of subsequence
// in an array with sum less than or equal to X
static int countSubsequence(int[] A, int N, int X)
{
// Initialize a DP array
int [,]dp = new int[N, X + 1];
for(int i = 0; i < N; i++)
{
for(int j = 0; j < X + 1; j++)
{
dp[i, j] = -1;
}
}
// Return the result
return countSubsequenceUtil(0, X, A,
N, dp) - 1;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 25, 13, 40 };
int X = 50;
int N = arr.Length;
Console.Write(countSubsequence(arr, N, X));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to count number
// of subsequences in an array
// with sum less than or equal to X
// Utility function to return the count
// of subsequence in an array with sum
// less than or equal to X
function countSubsequenceUtil(ind, sum, A, N, dp)
{
// Base condition
if (ind == N)
return 1;
// Return if the sub-problem
// is already calculated
if (dp[ind][sum] != -1)
return dp[ind][sum];
// Check if the current element is
// less than or equal to sum
if (A[ind] <= sum)
{
// Count subsequences excluding
// the current element
dp[ind][sum] = countSubsequenceUtil(
ind + 1, sum,
A, N, dp) +
// Count subsequences
// including the current
// element
countSubsequenceUtil(
ind + 1,
sum - A[ind],
A, N, dp);
}
else
{
// Exclude current element
dp[ind][sum] = countSubsequenceUtil(
ind + 1, sum,
A, N, dp);
}
// Return the result
return dp[ind][sum];
}
// Function to return the count of subsequence
// in an array with sum less than or equal to X
function countSubsequence(A, N, X)
{
// Initialize a DP array
let dp = new Array(N);
for(var i = 0; i < dp.length; i++)
{
dp[i] = new Array(2);
}
for(let i = 0; i < N; i++)
{
for(let j = 0; j < X + 1; j++)
{
dp[i][j] = -1;
}
}
// Return the result
return countSubsequenceUtil(0, X, A,
N, dp) - 1;
}
// Driver Code
let arr = [ 25, 13, 40 ], X = 50;
let N = arr.length;
document.write(countSubsequence(arr, N, X));
// This code is contributed by susmitakundugoaldanga
</script>
Python3
# Python program for the above approach: ## Utility function to return the count ## of subsequence in an array with sum ## less than or equal to X def countSubsequenceUtil(ind, s, A, N, dp): ## Base condition if (ind == N): return 1 ## Return if the sub-problem ## is already calculated if (dp[ind][s] != -1): return dp[ind][s] ## Check if the current element is ## less than or equal to sum if (A[ind] <= s): ## Count subsequences excluding ## the current element ## Also, Count subsequences including ## the current element dp[ind][s] = countSubsequenceUtil(ind + 1, s, A, N, dp) + countSubsequenceUtil(ind + 1, s - A[ind], A, N, dp) else: ## Exclude current element dp[ind][s] = countSubsequenceUtil(ind + 1, s, A, N, dp) ## Return the result return dp[ind][s] ## Function to return the count of subsequence ## in an array with sum less than or equal to X def countSubsequence(A, N, X): ## Initialize a DP array dp = [[-1 for _ in range(X + 1)] for i in range(N)] ## Return the result return countSubsequenceUtil(0, X, A, N, dp) - 1 ## Driver code if __name__=='__main__': arr = [25, 13, 40] X = 50 N = len(arr) print(countSubsequence(arr, N, X))
Producción:
4
Complejidad de tiempo: O(N*X)
Espacio Auxiliar: O(N*X)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA