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