Dada una array arr[] de N enteros y dos números K y S , la tarea es imprimir toda la subsecuencia de longitud K con la suma S .
Ejemplos:
Entrada: N = 5, K = 3, S = 20, arr[] = {4, 6, 8, 2, 12}
Salida:
{6, 2, 12}
Explicación:
Solo una subsecuencia de tamaño 3 con suma 20 es posible, es decir, {6, 2, 12} y la suma es 6 + 2 + 12 = 20
Entrada: N = 10, K = 5, S = 25, arr[] = {2, 4, 6, 8, 10, 12, 1, 2, 5, 7}
Salida:
{10, 1, 2, 5, 7}
{4, 8, 1, 5, 7}
{4, 8, 10, 1, 2}
{4, 6, 12, 1, 2}
{4, 6, 8, 2, 5}
{2, 10, 1, 5, 7}
{2, 8, 12, 1, 2}
{2, 6, 10, 2, 5}
{2, 6, 8, 2, 7}
{2, 4, 12, 2, 5}
{2, 4, 10, 2, 7}
{2, 4, 8, 10, 1}
{2, 4, 6 , 12, 1}
{2, 4, 6, 8, 5}
Enfoque: La idea es usar Backtracking para imprimir toda la subsecuencia con la suma S dada . A continuación se muestran los pasos:
- Iterar por todo el valor de la array arr[] y hacer lo siguiente:
- Si incluimos el elemento actual en la subsecuencia resultante, entonces, disminuya K y el valor anterior del elemento actual a la suma S.
- Itere recursivamente desde el siguiente índice del elemento hasta el final de la array para encontrar la subsecuencia resultante.
- Si K es 0 y S es 0 , entonces obtuvimos nuestra subsecuencia resultante de longitud K y suma S , imprimimos esta subsecuencia y retrocedemos para la siguiente subsecuencia resultante.
- Si no incluimos el elemento actual, encuentre la subsecuencia resultante excluyendo el elemento actual y repitiendo el procedimiento anterior para el resto del elemento en la array.
- La array resultante en los pasos 3 dará todas las subsecuencias posibles de longitud K con la suma S dada .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all the subsequences
// of a given length and having sum S
void comb(int* arr, int len, int r,
int ipos, int* op, int opos,
int sum)
{
// Termination condition
if (opos == r) {
int sum2 = 0;
for (int i = 0; i < opos; i++) {
// Add value to sum
sum2 = sum2 + op[i];
}
// Check if the resultant sum
// equals to target sum
if (sum == sum2) {
// If true
for (int i = 0; i < opos; i++)
// Print resultant array
cout << op[i] << ", ";
cout << endl;
}
// End this recursion stack
return;
}
if (ipos < len) {
// Check all the combinations
// using backtracking
comb(arr, len, r, ipos + 1,
op, opos, sum);
op[opos] = arr[ipos];
// Check all the combinations
// using backtracking
comb(arr, len, r, ipos + 1,
op, opos + 1, sum);
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 4, 6, 8, 2, 12 };
int K = 3;
int S = 20;
int N = sizeof(arr) / sizeof(arr[0]);
// To store the subsequence
int op[N] = { 0 };
// Function Call
comb(arr, N, K, 0, op, 0, S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find all the subsequences
// of a given length and having sum S
static void comb(int []arr, int len, int r,
int ipos, int[] op, int opos,
int sum)
{
// Termination condition
if (opos == r)
{
int sum2 = 0;
for(int i = 0; i < opos; i++)
{
// Add value to sum
sum2 = sum2 + op[i];
}
// Check if the resultant sum
// equals to target sum
if (sum == sum2)
{
// If true
for(int i = 0; i < opos; i++)
// Print resultant array
System.out.print(op[i] + ", ");
System.out.println();
}
// End this recursion stack
return;
}
if (ipos < len)
{
// Check all the combinations
// using backtracking
comb(arr, len, r, ipos + 1,
op, opos, sum);
op[opos] = arr[ipos];
// Check all the combinations
// using backtracking
comb(arr, len, r, ipos + 1,
op, opos + 1, sum);
}
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 4, 6, 8, 2, 12 };
int K = 3;
int S = 20;
int N = arr.length;
// To store the subsequence
int op[] = new int[N];
// Function Call
comb(arr, N, K, 0, op, 0, S);
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program for the above approach # Function to find all the subsequences # of a given length and having sum S def comb(arr, Len, r, ipos, op, opos, Sum): # Termination condition if (opos == r): sum2 = 0 for i in range(opos): # Add value to sum sum2 = sum2 + op[i] # Check if the resultant sum # equals to target sum if (Sum == sum2): # If true for i in range(opos): # Print resultant array print(op[i], end = ", ") print() # End this recursion stack return if (ipos < Len): # Check all the combinations # using backtracking comb(arr, Len, r, ipos + 1, op, opos, Sum) op[opos] = arr[ipos] # Check all the combinations # using backtracking comb(arr, Len, r, ipos + 1, op, opos + 1, Sum) # Driver code if __name__ == '__main__': # Given array arr = [ 4, 6, 8, 2, 12 ] K = 3 S = 20 N = len(arr) # To store the subsequence op = [0] * N # Function call comb(arr, N, K, 0, op, 0, S) # This code is contributed by himanshu77
C#
// C# program for the above approach
using System;
class GFG{
// Function to find all the subsequences
// of a given length and having sum S
static void comb(int []arr, int len, int r,
int ipos, int[] op, int opos,
int sum)
{
// Termination condition
if (opos == r)
{
int sum2 = 0;
for(int i = 0; i < opos; i++)
{
// Add value to sum
sum2 = sum2 + op[i];
}
// Check if the resultant sum
// equals to target sum
if (sum == sum2)
{
// If true
for(int i = 0; i < opos; i++)
// Print resultant array
Console.Write(op[i] + ", ");
Console.WriteLine();
}
// End this recursion stack
return;
}
if (ipos < len)
{
// Check all the combinations
// using backtracking
comb(arr, len, r, ipos + 1,
op, opos, sum);
op[opos] = arr[ipos];
// Check all the combinations
// using backtracking
comb(arr, len, r, ipos + 1,
op, opos + 1, sum);
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 4, 6, 8, 2, 12 };
int K = 3;
int S = 20;
int N = arr.Length;
// To store the subsequence
int []op = new int[N];
// Function call
comb(arr, N, K, 0, op, 0, S);
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript program for the above approach
// Function to find all the subsequences
// of a given length and having sum S
function comb(arr, len, r,
ipos, op, opos,
sum)
{
// Termination condition
if (opos == r)
{
let sum2 = 0;
for(let i = 0; i < opos; i++)
{
// Add value to sum
sum2 = sum2 + op[i];
}
// Check if the resultant sum
// equals to target sum
if (sum == sum2)
{
// If true
for(let i = 0; i < opos; i++)
// Print resultant array
document.write(op[i] + ", ");
document.write();
}
// End this recursion stack
return;
}
if (ipos < len)
{
// Check all the combinations
// using backtracking
comb(arr, len, r, ipos + 1,
op, opos, sum);
op[opos] = arr[ipos];
// Check all the combinations
// using backtracking
comb(arr, len, r, ipos + 1,
op, opos + 1, sum);
}
}
// Driver Code
// Given array
let arr = [ 4, 6, 8, 2, 12 ];
let K = 3;
let S = 20;
let N = arr.length;
// To store the subsequence
let op = Array.from({length: N}, (_, i) => 0);
// Function Call
comb(arr, N, K, 0, op, 0, S);
// This code is contributed by sanjoy_62.
</script>
Producción:
6, 2, 12,
Complejidad de tiempo: O(2^N * K)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por manavgoswami001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA