Dada una array de enteros, busque todas las combinaciones de cuatro elementos en la array cuya suma sea igual a un valor dado X.
Por ejemplo, si la array dada es {10, 2, 3, 4, 5, 9, 7, 8} y X = 23, entonces su función debería imprimir «3 5 7 8» (3 + 5 + 7 + 8 = 23).
Una solución ingenua es generar todos los cuádruples posibles y comparar la suma de cada cuádruple con X. El siguiente código implementa este método simple usando cuatro bucles anidados
C++
// C++ program for naive solution to
// print all combination of 4 elements
// in A[] with sum equal to X
#include <bits/stdc++.h>
using namespace std;
/* A naive solution to print all combination
of 4 elements in A[]with sum equal to X */
void findFourElements(int A[], int n, int X)
{
// Fix the first element and find other three
for (int i = 0; i < n - 3; i++)
{
// Fix the second element and find other two
for (int j = i + 1; j < n - 2; j++)
{
// Fix the third element and find the fourth
for (int k = j + 1; k < n - 1; k++)
{
// find the fourth
for (int l = k + 1; l < n; l++)
if (A[i] + A[j] + A[k] + A[l] == X)
cout << A[i] <<", " << A[j]
<< ", " << A[k] << ", " << A[l];
}
}
}
}
// Driver Code
int main()
{
int A[] = {10, 20, 30, 40, 1, 2};
int n = sizeof(A) / sizeof(A[0]);
int X = 91;
findFourElements (A, n, X);
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// C implementation of above approach
#include <stdio.h>
/* A naive solution to print all combination of 4 elements in A[]
with sum equal to X */
void findFourElements(int A[], int n, int X)
{
// Fix the first element and find other three
for (int i = 0; i < n-3; i++)
{
// Fix the second element and find other two
for (int j = i+1; j < n-2; j++)
{
// Fix the third element and find the fourth
for (int k = j+1; k < n-1; k++)
{
// find the fourth
for (int l = k+1; l < n; l++)
if (A[i] + A[j] + A[k] + A[l] == X)
printf("%d, %d, %d, %d", A[i], A[j], A[k], A[l]);
}
}
}
}
// Driver program to test above function
int main()
{
int A[] = {10, 20, 30, 40, 1, 2};
int n = sizeof(A) / sizeof(A[0]);
int X = 91;
findFourElements (A, n, X);
return 0;
}
Java
// Java implementation of above approach
class FindFourElements
{
/* A naive solution to print all combination of 4 elements in A[]
with sum equal to X */
void findFourElements(int A[], int n, int X)
{
// Fix the first element and find other three
for (int i = 0; i < n - 3; i++)
{
// Fix the second element and find other two
for (int j = i + 1; j < n - 2; j++)
{
// Fix the third element and find the fourth
for (int k = j + 1; k < n - 1; k++)
{
// find the fourth
for (int l = k + 1; l < n; l++)
{
if (A[i] + A[j] + A[k] + A[l] == X)
System.out.print(A[i]+" "+A[j]+" "+A[k]
+" "+A[l]);
}
}
}
}
}
// Driver program to test above functions
public static void main(String[] args)
{
FindFourElements findfour = new FindFourElements();
int A[] = {10, 20, 30, 40, 1, 2};
int n = A.length;
int X = 91;
findfour.findFourElements(A, n, X);
}
}
Python3
#Python 3 implementation of above approach
# A naive solution to print all combination
# of 4 elements in A[] with sum equal to X
def findFourElements(A, n, X):
# Fix the first element and find
# other three
for i in range(0,n-3):
# Fix the second element and
# find other two
for j in range(i+1,n-2):
# Fix the third element
# and find the fourth
for k in range(j+1,n-1):
# find the fourth
for l in range(k+1,n):
if A[i] + A[j] + A[k] + A[l] == X:
print ("%d, %d, %d, %d"
%( A[i], A[j], A[k], A[l]))
# Driver program to test above function
A = [10, 2, 3, 4, 5, 9, 7, 8]
n = len(A)
X = 23
findFourElements (A, n, X)
# This code is contributed by shreyanshi_arun
C#
// C# program for naive solution to
// print all combination of 4 elements
// in A[] with sum equal to X
using System;
class FindFourElements
{
void findFourElements(int []A, int n, int X)
{
// Fix the first element and find other three
for (int i = 0; i < n - 3; i++)
{
// Fix the second element and find other two
for (int j = i + 1; j < n - 2; j++)
{
// Fix the third element and find the fourth
for (int k = j + 1; k < n - 1; k++)
{
// find the fourth
for (int l = k + 1; l < n; l++)
{
if (A[i] + A[j] + A[k] + A[l] == X)
Console.Write(A[i] + " " + A[j] +
" " + A[k] + " " + A[l]);
}
}
}
}
}
// Driver program to test above functions
public static void Main()
{
FindFourElements findfour = new FindFourElements();
int []A = {10, 20, 30, 40, 1, 2};
int n = A.Length;
int X = 91;
findfour.findFourElements(A, n, X);
}
}
// This code is contributed by nitin mittal
PHP
<?php
// Php implementation of above approach
/* A naive solution to print all combination
of 4 elements in A[] with sum equal to X */
function findFourElements($A, $n, $X)
{
// Fix the first element and find other
// three
for ($i = 0; $i < $n-3; $i++)
{
// Fix the second element and find
// other two
for ($j = $i+1; $j < $n-2; $j++)
{
// Fix the third element and
// find the fourth
for ($k = $j+1; $k < $n-1; $k++)
{
// find the fourth
for ($l = $k+1; $l < $n; $l++)
if ($A[$i] + $A[$j] +
$A[$k] + $A[$l] == $X)
echo $A[$i], ", " , $A[$j],
", ", $A[$k], ", ", $A[$l];
}
}
}
}
// Driver program to test above function
$A = array (10, 20, 30, 40, 1, 2);
$n = sizeof($A) ;
$X = 91;
findFourElements ($A, $n, $X);
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program for the above approach
/* A naive solution to print all combination
of 4 elements in A[]with sum equal to X */
function findFourElements(A, n, X)
{
// Fix the first element and find other three
for (let i = 0; i < n - 3; i++)
{
// Fix the second element and find other two
for (let j = i + 1; j < n - 2; j++)
{
// Fix the third element and find the fourth
for (let k = j + 1; k < n - 1; k++)
{
// find the fourth
for (let l = k + 1; l < n; l++)
if (A[i] + A[j] + A[k] + A[l] == X)
document.write(A[i]+", "+A[j]+", "+A[k] +", "+A[l]);
}
}
}
}
// Driver Code
let A = [10, 20, 30, 40, 1, 2];
let n = A.length;
let X = 91;
findFourElements (A, n, X);
</script>
C++
// C++ program for to print all combination
// of 4 elements in A[] with sum equal to X
#include<bits/stdc++.h>
using namespace std;
/* Following function is needed
for library function qsort(). */
int compare (const void *a, const void * b)
{
return ( *(int *)a - *(int *)b );
}
/* A sorting based solution to print
all combination of 4 elements in A[]
with sum equal to X */
void find4Numbers(int A[], int n, int X)
{
int l, r;
// Sort the array in increasing
// order, using library function
// for quick sort
qsort (A, n, sizeof(A[0]), compare);
/* Now fix the first 2 elements
one by one and find
the other two elements */
for (int i = 0; i < n - 3; i++)
{
for (int j = i+1; j < n - 2; j++)
{
// Initialize two variables as
// indexes of the first and last
// elements in the remaining elements
l = j + 1;
r = n-1;
// To find the remaining two
// elements, move the index
// variables (l & r) toward each other.
while (l < r)
{
if( A[i] + A[j] + A[l] + A[r] == X)
{
cout << A[i]<<", " << A[j] <<
", " << A[l] << ", " << A[r];
l++; r--;
}
else if (A[i] + A[j] + A[l] + A[r] < X)
l++;
else // A[i] + A[j] + A[l] + A[r] > X
r--;
} // end of while
} // end of inner for loop
} // end of outer for loop
}
/* Driver code */
int main()
{
int A[] = {1, 4, 45, 6, 10, 12};
int X = 21;
int n = sizeof(A) / sizeof(A[0]);
find4Numbers(A, n, X);
return 0;
}
// This code is contributed by rathbhupendra
C
# include <stdio.h>
# include <stdlib.h>
/* Following function is needed for library function qsort(). Refer
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
int compare (const void *a, const void * b)
{ return ( *(int *)a - *(int *)b ); }
/* A sorting based solution to print all combination of 4 elements in A[]
with sum equal to X */
void find4Numbers(int A[], int n, int X)
{
int l, r;
// Sort the array in increasing order, using library
// function for quick sort
qsort (A, n, sizeof(A[0]), compare);
/* Now fix the first 2 elements one by one and find
the other two elements */
for (int i = 0; i < n - 3; i++)
{
for (int j = i+1; j < n - 2; j++)
{
// Initialize two variables as indexes of the first and last
// elements in the remaining elements
l = j + 1;
r = n-1;
// To find the remaining two elements, move the index
// variables (l & r) toward each other.
while (l < r)
{
if( A[i] + A[j] + A[l] + A[r] == X)
{
printf("%d, %d, %d, %d", A[i], A[j],
A[l], A[r]);
l++; r--;
}
else if (A[i] + A[j] + A[l] + A[r] < X)
l++;
else // A[i] + A[j] + A[l] + A[r] > X
r--;
} // end of while
} // end of inner for loop
} // end of outer for loop
}
/* Driver program to test above function */
int main()
{
int A[] = {1, 4, 45, 6, 10, 12};
int X = 21;
int n = sizeof(A)/sizeof(A[0]);
find4Numbers(A, n, X);
return 0;
}
Java
import java.util.Arrays;
class FindFourElements
{
/* A sorting based solution to print all combination of 4 elements in A[]
with sum equal to X */
void find4Numbers(int A[], int n, int X)
{
int l, r;
// Sort the array in increasing order, using library
// function for quick sort
Arrays.sort(A);
/* Now fix the first 2 elements one by one and find
the other two elements */
for (int i = 0; i < n - 3; i++)
{
for (int j = i + 1; j < n - 2; j++)
{
// Initialize two variables as indexes of the first and last
// elements in the remaining elements
l = j + 1;
r = n - 1;
// To find the remaining two elements, move the index
// variables (l & r) toward each other.
while (l < r)
{
if (A[i] + A[j] + A[l] + A[r] == X)
{
System.out.println(A[i]+" "+A[j]+" "+A[l]+" "+A[r]);
l++;
r--;
}
else if (A[i] + A[j] + A[l] + A[r] < X)
l++;
else // A[i] + A[j] + A[l] + A[r] > X
r--;
} // end of while
} // end of inner for loop
} // end of outer for loop
}
// Driver program to test above functions
public static void main(String[] args)
{
FindFourElements findfour = new FindFourElements();
int A[] = {1, 4, 45, 6, 10, 12};
int n = A.length;
int X = 21;
findfour.find4Numbers(A, n, X);
}
}
// This code has been contributed by Mayank Jaiswal
Python 3
# A sorting based solution to print all combination # of 4 elements in A[] with sum equal to X def find4Numbers(A, n, X): # Sort the array in increasing order, # using library function for quick sort A.sort() # Now fix the first 2 elements one by # one and find the other two elements for i in range(n - 3): for j in range(i + 1, n - 2): # Initialize two variables as indexes # of the first and last elements in # the remaining elements l = j + 1 r = n - 1 # To find the remaining two elements, # move the index variables (l & r) # toward each other. while (l < r): if(A[i] + A[j] + A[l] + A[r] == X): print(A[i], ",", A[j], ",", A[l], ",", A[r]) l += 1 r -= 1 elif (A[i] + A[j] + A[l] + A[r] < X): l += 1 else: # A[i] + A[j] + A[l] + A[r] > X r -= 1 # Driver Code if __name__ == "__main__": A = [1, 4, 45, 6, 10, 12] X = 21 n = len(A) find4Numbers(A, n, X) # This code is contributed by ita_c
C#
// C# program for to print all combination
// of 4 elements in A[] with sum equal to X
using System;
class FindFourElements
{
// A sorting based solution to print all
// combination of 4 elements in A[] with
// sum equal to X
void find4Numbers(int []A, int n, int X)
{
int l, r;
// Sort the array in increasing order,
// using library function for quick sort
Array.Sort(A);
/* Now fix the first 2 elements one by one
and find the other two elements */
for (int i = 0; i < n - 3; i++)
{
for (int j = i + 1; j < n - 2; j++)
{
// Initialize two variables as indexes of
// the first and last elements in the
// remaining elements
l = j + 1;
r = n - 1;
// To find the remaining two elements, move the
// index variables (l & r) toward each other.
while (l < r)
{
if (A[i] + A[j] + A[l] + A[r] == X)
{
Console.Write(A[i] + " " + A[j] +
" " + A[l] + " " + A[r]);
l++;
r--;
}
else if (A[i] + A[j] + A[l] + A[r] < X)
l++;
else // A[i] + A[j] + A[l] + A[r] > X
r--;
} // end of while
} // end of inner for loop
} // end of outer for loop
}
// Driver program to test above functions
public static void Main()
{
FindFourElements findfour = new FindFourElements();
int []A = {1, 4, 45, 6, 10, 12};
int n = A.Length;
int X = 21;
findfour.find4Numbers(A, n, X);
}
}
// This code has been contributed by nitin mittal
PHP
<?php
// PHP program for to print all
// combination of 4 elements in
// A[] with sum equal to X
// A sorting based solution to
// print all combination of 4
// elements in A[] with sum
// equal to X
function find4Numbers($A, $n, $X)
{
$l; $r;
// Sort the array in increasing
// order, using library function
// for quick sort
sort($A);
// Now fix the first 2 elements
// one by one and find the other
// two elements
for ($i = 0; $i < $n - 3; $i++)
{
for ($j = $i + 1; $j < $n - 2; $j++)
{
// Initialize two variables
// as indexes of the first
// and last elements in the
// remaining elements
$l = $j + 1;
$r = $n - 1;
// To find the remaining two
// elements, move the index
// variables (l & r) towards
// each other.
while ($l < $r)
{
if ($A[$i] + $A[$j] +
$A[$l] + $A[$r] == $X)
{
echo $A[$i] , " " , $A[$j] ,
" " , $A[$l] ,
" " , $A[$r];
$l++;
$r--;
}
else if ($A[$i] + $A[$j] +
$A[$l] + $A[$r] < $X)
$l++;
// A[i] + A[j] + A[l] + A[r] > X
else
$r--;
}
}
}
}
// Driver Code
$A = array(1, 4, 45, 6, 10, 12);
$n = count($A);
$X = 21;
find4Numbers($A, $n, $X);
// This code is contributed
// by nitin mittal
?>
Javascript
<script>
/* A sorting based solution to print all combination of 4 elements in A[]
with sum equal to X */
function find4Numbers(A,n,X)
{
let l, r;
// Sort the array in increasing order, using library
// function for quick sort
A.sort(function(a, b){return a - b});
/* Now fix the first 2 elements one by one and find
the other two elements */
for (let i = 0; i < n - 3; i++)
{
for (let j = i + 1; j < n - 2; j++)
{
// Initialize two variables as indexes of the first and last
// elements in the remaining elements
l = j + 1;
r = n - 1;
// To find the remaining two elements, move the index
// variables (l & r) toward each other.
while (l < r)
{
if (A[i] + A[j] + A[l] + A[r] == X)
{
document.write(A[i]+" "+A[j]+" "+A[l]+" "+A[r]+"<br>");
l++;
r--;
}
else if ((A[i] + A[j] + A[l] + A[r]) < X)
{
l++;
}
else // A[i] + A[j] + A[l] + A[r] > X
{
r--;
}
} // end of while
} // end of inner for loop
}// end of outer for loop
}
// Driver program to test above functions
let A= [1, 4, 45, 6, 10, 12];
let n = A.length;
let X = 21;
find4Numbers(A, n, X)
// This code is contributed by rag2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA