배열을 합이 같은 두 개의 하위 배열로 나눌 수 있는지 확인

정수 배열이 주어지면 배열을 동일한 합계를 갖는 두 개의 하위 배열로 나누는 배열에서 정확히 하나의 정수를 제거하는 것이 가능한지 찾아보세요.

예:

  Input:    arr = [6 2 3 2 1]   Output:    true   Explanation:    On removing element 2 at index 1 the array gets divided into two subarrays [6] and [3 2 1] having equal sum   Input:    arr = [6 1 3 2 5]   Output:    true   Explanation:    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:   true   Explanation:    On removing element 6 at index 0 the array gets divided into two sets [] and [-2 -3 2 3] having equal sum   Input:    arr = [6 -2 3 2 3]   Output:   false

에이 순진한 해결책 배열의 모든 요소를 고려하여 왼쪽과 오른쪽 합계를 계산하고 왼쪽과 오른쪽 합계가 같은 것으로 확인되면 true를 반환하는 것입니다. 이 솔루션의 시간 복잡도는 O(n²).

그만큼 효율적인 솔루션 배열의 모든 요소의 합계를 미리 계산하는 작업이 포함됩니다. 그런 다음 배열의 각 요소에 대해 배열 요소의 총합에서 지금까지 찾은 요소의 합을 뺀 값을 사용하여 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    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 sumnThe'  ' 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 sumnThe'  +' 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# 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 sumnThe 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 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 sumnThe'. ' 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 ' + '
' + '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' + '
');    return false;  }    let arr = [6 2 3 2 1];  let n = arr.length;  divideArray(arr n);   </script>

산출

The array can be divided intotwo subarrays with equal sum The two subarrays are - [ 6 ] [ 3 2 1 ]