查找数组是否可以划分为两个等和子数组-yiteyi-C++库

给定一个整数数组，找出是否有可能从数组中删除一个整数，该数组将数组分成两个具有相同和的子数组。例如：

null

Input:  arr = [6, 2, 3, 2, 1]Output:  trueExplanation:  On removing element 2 at index 1,the array gets divided into two subarrays [6] and [3, 2, 1] having equal sumInput:  arr = [6, 1, 3, 2, 5]Output:  trueExplanation:  On removing element 3 at index 2,the array gets divided into two subarrays [6, 1]and [2, 5] having equal sum.Input:  arr = [6, -2, -3, 2, 3]Output: trueExplanation:  On removing element 6 at index 0, the array gets divided into two sets [] and [-2, -3, 2, 3] having equal sumInput:  arr = [6, -2, 3, 2, 3]Output: false

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 天真的解决方案 将考虑数组的所有元素，并计算它们的左和右和返回true，如果左和右的总和被发现是相等的。这个解决方案的时间复杂度为O（n） ^2. ). 这个 有效解决方案 包括提前计算数组中所有元素的总和。然后，对于数组中的每个元素，我们可以使用数组元素的总和减去到目前为止找到的元素之和来计算它在O（1）时间内的右和。这个解的时间复杂度为O（n），它使用的辅助空间为O（1）。以下是上述方法的实施情况：

C++

                         // C++ program to divide the array into two                       
                         // subarrays with the same sum on removing                       
                         // exactly one integer from the array                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // Utility function to print the sub-array                       
                         void                                     printSubArray(                                     int                                     arr[],                                     int                                     start,                                     int                                     end)                       
                         {                       
                                                 cout <<                                     "[ "                                     ;                       
                                                 for                                     (                                     int                                     i = start; i <= end; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 cout <<                                     "] "                                     ;                       
                         }                       
           
                         // Function that divides the array into two subarrays                       
                         // with the same sum                       
                         bool                                     divideArray(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // sum stores sum of all elements of the array                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 sum += arr[i];                       
           
                                                 // sum stores sum till previous index of the array                       
                                                 int                                     sum_so_far = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // If on removing arr[i], we get equals left                       
                                                 // and right half                       
                                                 if                                     (2 * sum_so_far + arr[i] == sum)                       
                                                 {                       
                                                 cout << "The array can be divided into                       
                                                 "two subarrays with equal sumThe"                       
                                                 " two subarrays are - "                                     ;                       
                                                 printSubArray(arr, 0, i - 1);                       
                                                 printSubArray(arr, i + 1, n - 1);                       
           
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 // add current element to sum_so_far                       
                                                 sum_so_far += arr[i];                       
                                                 }                       
           
                                                 // The array cannot be divided                       
                                                 cout <<                                     "The array cannot be divided into two "                       
                                                 "subarrays with equal sum"                                     ;                       
           
                                                 return                                     false                                     ;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {6, 2, 3, 2, 1};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
           
                                                 divideArray(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to divide the array into two                       
                         // subarrays with the same sum on removing                       
                         // exactly one integer from the array                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Utility function to print the sub-array                       
                                                 static                                     void                                     printSubArray(                                     int                                     arr[],                                     int                                     start,                                     int                                     end)                       
                                                 {                       
                                                 System.out.print(                                     "[ "                                     );                       
                                                 for                                     (                                     int                                     i = start; i <= end; i++)                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
                                                 System.out.print(                                     "] "                                     );                       
                                                 }                       
                                   
                                                 // Function that divides the array into two subarrays                       
                                                 // with the same sum                       
                                                 static                                     boolean                                     divideArray(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 // sum stores sum of all elements of the array                       
                                                 int                                     sum =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 sum += arr[i];                       
                                   
                                                 // sum stores sum till previous index of the array                       
                                                 int                                     sum_so_far =                                     0                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 // If on removing arr[i], we get equals left                       
                                                 // and right half                       
                                                 if                                     (                                     2                                     * sum_so_far + arr[i] == sum)                       
                                                 {                       
                                                 System.out.print(                                     "The array can be divided into "                       
                                                 +                                     "two subarrays with equal sumThe"                       
                                                 +                                     " two subarrays are - "                                     );                       
                                                 printSubArray(arr,                                     0                                     , i -                                     1                                     );                       
                                                 printSubArray(arr, i +                                     1                                     , n -                                     1                                     );                       
                                   
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 // add current element to sum_so_far                       
                                                 sum_so_far += arr[i];                       
                                                 }                       
                                   
                                                 // The array cannot be divided                       
                                                 System.out.println(                                     "The array cannot be divided into two "                       
                                                 +                                     "subarrays with equal sum"                                     );                       
                                   
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     6                                     ,                                     2                                     ,                                     3                                     ,                                     2                                     ,                                     1                                     };                       
                                                 int                                     n = arr.length;                       
                                   
                                                 divideArray(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Pramod Kumar                       

Python3

                         ''' Python3 program to divide the array                       
                         into two subarrays with the same sum on                       
                         removing exactly one integer from the array'''                       
           
                         # Utility function to print the sub-array                       
                         def                                     printSubArray(arr, start, end):                       
                                                 print                                     (                                     "[ "                                     , end                                     =                                     "")                       
                                                 for                                     i                                     in                                     range                                     (start, end                                     +                                     1                                     ):                       
                                                 print                                     (arr[i], end                                     =                                     " "                                     )                       
                                                 print                                     (                                     "]"                                     , end                                     =                                     "")                       
           
                         # Function that divides the array into                       
                         # two subarrays with the same sum                       
                         def                                     divideArray(arr, n):                       
           
                                                 # sum stores sum of all                       
                                                 # elements of the array                       
                                                 sum                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                                 sum                                     +                                     =                                     arr[i]                       
           
                                                 # sum stores sum till previous                       
                                                 # index of the array                       
                                                 sum_so_far                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
           
                                                 # If on removing arr[i], we get                       
                                                 # equals left and right half                       
                                                 if                                     2                                     *                                     sum_so_far                                     +                                     arr[i]                                     =                                     =                                     sum                                     :                       
                                                 print                                     (                                     "The array can be divided into"                                     ,                       
                                                 "two subarrays with equal sum"                                     )                       
                                                 print                                     (                                     "two subarrays are -"                                     , end                                     =                                     "")                       
                                                 printSubArray(arr,                                     0                                     , i                                     -                                     1                                     )                       
                                                 printSubArray(arr, i                                     +                                     1                                     , n                                     -                                     1                                     )                       
                                                 return                                     True                       
           
                                                 # add current element to sum_so_far                       
                                                 sum_so_far                                     +                                     =                                     arr[i]                       
           
                                                 # The array cannot be divided                       
                                                 print                                     (                                     "The array cannot be divided into"                       
                                                 "two subarrays with equal sum"                                     , end                                     =                                     "")                       
           
                                                 return                                     False                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     6                                     ,                                     2                                     ,                                     3                                     ,                                     2                                     ,                                     1                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         divideArray(arr, n)                       
           
                         # This code is contributed by Shreyanshi Arun                       

C#

                         // C# program to divide the array into two                       
                         // subarrays with the same sum on removing                       
                         // exactly one integer from the array                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Utility function to print the sub-array                       
                                                 static                                     void                                     printSubArray(                                     int                                     []arr,                       
                                                 int                                     start,                                     int                                     end)                       
                                                 {                       
                                                 Console.Write(                                     "[ "                                     );                       
                                                 for                                     (                                     int                                     i = start; i <= end; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 Console.Write(                                     "] "                                     );                       
                                                 }                       
                                   
                                                 // Function that divides the array into                       
                                                 // two subarrays with the same sum                       
                                                 static                                     bool                                     divideArray(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                   
                                                 // sum stores sum of all elements of                       
                                                 // the array                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 sum += arr[i];                       
           
                                                 // sum stores sum till previous index                       
                                                 // of the array                       
                                                 int                                     sum_so_far = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // If on removing arr[i], we get                       
                                                 // equals left and right half                       
                                                 if                                     (2 * sum_so_far + arr[i] == sum)                       
                                                 {                       
                                                 Console.Write(                                     "The array can be"                       
                                                 +                                     " divided into two subarrays"                       
                                                 +                                     " with equal sumThe two"                       
                                                 +                                     " subarrays are - "                                     );                       
                                                 printSubArray(arr, 0, i - 1);                       
                                                 printSubArray(arr, i + 1, n - 1);                       
           
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 // add current element to sum_so_far                       
                                                 sum_so_far += arr[i];                       
                                                 }                       
           
                                                 // The array cannot be divided                       
                                                 Console.WriteLine(                                     "The array cannot be"                       
                                                 +                                     " divided into two subarrays with "                       
                                                 +                                     "equal sum"                                     );                       
                                   
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     []arr = {6, 2, 3, 2, 1};                       
                                                 int                                     n = arr.Length;                       
           
                                                 divideArray(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

PHP

                         <?php                       
                         // PHP program to divide the array into two                       
                         // subarrays with the same sum on removing                       
                         // exactly one integer from the array                       
           
                         // Utility function to print the sub-array                       
                         function                                     printSubArray(                                     $arr                                     ,                                     $start                                     ,                                     $end                                     )                       
                         {                       
                                                 echo                                     "[ "                                     ;                       
                                                 for                                     (                                     $i                                     =                                     $start                                     ;                                     $i                                     <=                                     $end                                     ;                                     $i                                     ++)                       
                                                 echo                                     $arr                                     [                                     $i                                     ] .                                     " "                                     ;                       
                                                 echo                                     "] "                                     ;                       
                         }                       
           
                         // Function that divides the                       
                         // array into two subarrays                       
                         // with the same sum                       
                         function                                     divideArray(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 // sum stores sum of all                       
                                                 // elements of the array                       
                                                 $sum                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $sum                                     +=                                     $arr                                     [                                     $i                                     ];                       
           
                                                 // sum stores sum till previous                       
                                                 // index of the array                       
                                                 $sum_so_far                                     = 0;                       
           
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                   
                                                 // If on removing arr[i],                       
                                                 // we get equals left                       
                                                 // and right half                       
                                                 if                                     (2 *                                     $sum_so_far                                     +                                     $arr                                     [                                     $i                                     ] ==                                     $sum                                     )                       
                                                 {                       
                                                 echo                                     "The array can be divided into"                                     .                       
                                                 "two subarrays with equal sumThe"                                     .                       
                                                 " two subarrays are - "                                     ;                       
                                                 printSubArray(                                     $arr                                     , 0,                                     $i                                     - 1);                       
                                                 printSubArray(                                     $arr                                     ,                                     $i                                     + 1,                                     $n                                     - 1);                       
           
                                                 return                                     true;                       
                                                 }                       
                                   
                                                 // add current element                       
                                                 // to sum_so_far                       
                                                 $sum_so_far                                     +=                                     $arr                                     [                                     $i                                     ];                       
                                                 }                       
           
                                                 // The array cannot be divided                       
                                                 echo                                     "The array cannot be divided into two "                                     .                       
                                                 "subarrays with equal sum"                                     ;                       
           
                                                 return                                     false;                       
                         }                       
           
                                                 // Driver code                       
                                                 $arr                                     =                                     array                                     (6, 2, 3, 2, 1);                       
                                                 $n                                     = sizeof(                                     $arr                                     );                       
           
                                                 divideArray(                                     $arr                                     ,                                     $n                                     );                       
                                   
                         // This code is contributed by Anuj_67                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // JavaScript program to divide the array into two                       
                                                 // subarrays with the same sum on removing                       
                                                 // exactly one integer from the array                       
                                   
                                                 // Utility function to print the sub-array                       
                                                 function                                     printSubArray(arr, start, end)                       
                                                 {                       
                                                 document.write(                                     "[ "                                     );                       
                                                 for                                     (let i = start; i <= end; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                                                 document.write(                                     "] "                                     );                       
                                                 }                       
                                   
                                                 // Function that divides the array into                       
                                                 // two subarrays with the same sum                       
                                                 function                                     divideArray(arr, n)                       
                                                 {                       
                                   
                                                 // sum stores sum of all elements of                       
                                                 // the array                       
                                                 let sum = 0;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 sum += arr[i];                       
                                   
                                                 // sum stores sum till previous index                       
                                                 // of the array                       
                                                 let sum_so_far = 0;                       
                                   
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // If on removing arr[i], we get                       
                                                 // equals left and right half                       
                                                 if                                     (2 * sum_so_far + arr[i] == sum)                       
                                                 {                       
                                                 document.write(                                     "The array can be"                       
                                                 +                                     " divided into two subarrays"                       
                                                 +                                     " with equal sum "                                     +                                     "</br>"                                     +                                     "The two"                       
                                                 +                                     " sets are - "                                     );                       
                                                 printSubArray(arr, 0, i - 1);                       
                                                 printSubArray(arr, i + 1, n - 1);                       
                                   
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 // add current element to sum_so_far                       
                                                 sum_so_far += arr[i];                       
                                                 }                       
                                   
                                                 // The array cannot be divided                       
                                                 document.write(                                     "The array cannot be"                       
                                                 +                                     " divided into two subarrays with "                       
                                                 +                                     "equal sum"                                     +                                     "</br>"                                     );                       
                                   
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 let arr = [6, 2, 3, 2, 1];                       
                                                 let n = arr.length;                       
           
                                                 divideArray(arr, n);                       
                                   
                         </script>                       

输出：

The array can be divided into two subarrays with equal sumThe two sets are - [6] [3 2 1]

本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章