配列を2つのサブ配列に最適に分割して、両方のサブ配列の要素の合計が同じになるようにするにはどうすればよいですか。そうでない場合、エラーが発生します。
与えられた配列
10, 20 , 30 , 5 , 40 , 50 , 40 , 15
それは次のように分けることができます
10, 20, 30, 5, 40
と
50, 40, 15
各サブアレイの合計は最大105です。
10, 20, 30, 5, 40, 50, 40, 10
配列を等しい合計の2つの配列に分割することはできません。
で実行される動的計画法を含むソリューションが存在しますO(n*TotalSum)。ここnで、は配列内の要素の数であり、TotalSumはそれらの合計です。
最初の部分は、配列に要素を追加することによって作成できるすべての数値のセットを計算することです。
サイズの配列の場合n、これを、と呼びますT(n)。
T(n) = T(n-1) UNION { Array[n]+k | k is in T(n-1) }
（正しさの証明は、再帰関数のほとんどの場合と同様に、誘導によるものです。）
また、動的マトリックスの各セルについて、それを作成するために追加された要素を覚えておいてください。
単純な複雑さの分析は、これがで行われることを示しO(n*TotalSum)ます。
を計算した後T(n)、正確にサイズの要素をセットで検索しTotalSum / 2ます。
そのようなアイテムが存在する場合、それを作成した要素、合計されたTotalSum / 2要素は等しく、その作成の一部ではなかった要素も等しくなりますTotalSum / 2（TotalSum - TotalSum / 2 = TotalSum / 2）。
これは疑似多項式の解です。AFAIK、この問題がPにあることは知られていない。
これはパーティションの問題と呼ばれます。いくつかの特別な場合に最適なソリューションがあります。ただし、一般的に、これはNP完全問題です。
その一般的な変形では、この問題は2つの制約を課し、より簡単な方法で実行できます。
次に機能するアルゴリズムは次のとおりです。
次のコードは上記を実行します。
public boolean canBalance(int[] nums) {
int leftSum = 0, rightSum = 0, i, j;
if(nums.length == 1)
return false;
for(i=0, j=nums.length-1; i<=j ;){
if(leftSum <= rightSum){
leftSum+=nums[i];
i++;
}else{
rightSum+=nums[j];
j--;
}
}
return (rightSum == leftSum);
}
出力：
canBalance({1, 1, 1, 2, 1}) → true OK
canBalance({2, 1, 1, 2, 1}) → false OK
canBalance({10, 10}) → true OK
canBalance({1, 1, 1, 1, 4}) → true OK
canBalance({2, 1, 1, 1, 4}) → false OK
canBalance({2, 3, 4, 1, 2}) → false OK
canBalance({1, 2, 3, 1, 0, 2, 3}) → true OK
canBalance({1, 2, 3, 1, 0, 1, 3}) → false OK
canBalance({1}) → false OK
canBalance({1, 1, 1, 2, 1}) → true OK
もちろん、要素を順不同で組み合わせることができる場合、それはすべての複雑さを伴うパーティションの問題になります。
a=[int(g) for g in input().split()] #for taking the array as input in a
single line
leftsum=0
n=len(a)
for i in range(n):
leftsum+=a[i] #calculates the sum of first subarray
rightsum=0
for j in range(i+1):
rightsum+=a[j] #calculates the sum of other subarray
if leftsum==rightsum:
pos=i+1 #if the sum of subarrays are equal,
break set position where the condition
gets satisfied and exit the loop
else:
pos=-1 #if the sum of subarrays is not
equal, set position to -1
if pos=-1 or pos=n:
print('It is not possible.')
else: #printing the sub arrays`
for k in range(n):
if pos=k:
print('')
print(str(a[k]),end='')
この問題は、配列が要素の合計が同じである2つのサブ配列を持つことができる場合を示しています。したがって、ブール値を返す必要があります。効率的なアルゴリズムを見つけました：アルゴリズム：手順ステップ1：空の配列をコンテナーとして取得し、初期配列を並べ替えて、空の配列を保持します。ステップ2：動的に割り当て可能な2つの配列を取得し、補助配列から最高と2番目に高い配列を取り出して、それぞれ2つのサブ配列に保持し、補助配列から削除します。ステップ3：サブ配列内の要素の合計を比較します。小さい方の合計は、配列内の残りの最も高い要素をフェッチして、コンテナーから削除する可能性があります。ステップ4：コンテナーが空になるまで、ステップ3をループします。ステップ5：2つのサブ配列の合計を比較します。同じ場合はtrueを返し、そうでない場合はfalseを返します。
//この問題の複雑さは、多くの組み合わせが可能である可能性があることですが、このアルゴリズムには1つの独自の方法があります。
@Galサブセット和問題はNP完全であり、O（n * TotalSum）疑似多項式動的計画法アルゴリズムがあります。しかし、この問題はNP完全ではありません。これは特殊なケースであり、実際、これは線形時間で解決できます。
ここでは、配列を同じ合計で2つの部分に分割できるインデックスを探しています。次のコードを確認してください。
分析：O（n）、アルゴリズムは配列を反復処理するだけで、TotalSumを使用しないため。
public class EqualSumSplit {
public static int solution( int[] A ) {
int[] B = new int[A.length];
int[] C = new int[A.length];
int sum = 0;
for (int i=0; i< A.length; i++) {
sum += A[i];
B[i] = sum;
// System.out.print(B[i]+" ");
}
// System.out.println();
sum = 0;
for (int i=A.length-1; i>=0; i--) {
sum += A[i];
C[i] = sum;
// System.out.print(C[i]+" ");
}
// System.out.println();
for (int i=0; i< A.length-1; i++) {
if (B[i] == C[i+1]) {
System.out.println(i+" "+B[i]);
return i;
}
}
return -1;
}
public static void main(String args[] ) {
int[] A = {-7, 1, 2, 3, -4, 3, 0};
int[] B = {10, 20 , 30 , 5 , 40 , 50 , 40 , 15};
solution(A);
solution(B);
}
}
別の解決策を試しました。Wikiソリューション以外（パーティションの問題）。
static void subSet(int array[]) {
System.out.println("Input elements :" + Arrays.toString(array));
int sum = 0;
for (int element : array) {
sum = sum + element;
}
if (sum % 2 == 1) {
System.out.println("Invalid Pair");
return;
}
Arrays.sort(array);
System.out.println("Sorted elements :" + Arrays.toString(array));
int subSum = sum / 2;
int[] subSet = new int[array.length];
int tmpSum = 0;
boolean isFastpath = true;
int lastStopIndex = 0;
for (int j = array.length - 1; j >= 0; j--) {
tmpSum = tmpSum + array[j];
if (tmpSum == subSum) { // if Match found
if (isFastpath) { // if no skip required and straight forward
// method
System.out.println("Found SubSets 0..." + (j - 1) + " and "
+ j + "..." + (array.length - 1));
} else {
subSet[j] = array[j];
array[j] = 0;
System.out.println("Found..");
System.out.println("Set 1" + Arrays.toString(subSet));
System.out.println("Set 2" + Arrays.toString(array));
}
return;
} else {
// Either the tmpSum greater than subSum or less .
// if less , just look for next item
if (tmpSum < subSum && ((subSum - tmpSum) >= array[0])) {
if (lastStopIndex > j && subSet[lastStopIndex] == 0) {
subSet[lastStopIndex] = array[lastStopIndex];
array[lastStopIndex] = 0;
}
lastStopIndex = j;
continue;
}
isFastpath = false;
if (subSet[lastStopIndex] == 0) {
subSet[lastStopIndex] = array[lastStopIndex];
array[lastStopIndex] = 0;
}
tmpSum = tmpSum - array[j];
}
}
}
私はテストしました。（0より大きい正の数でうまく機能します）問題が発生した場合はお知らせください。
これは問題の再帰的ソリューションです。1つの非再帰的ソリューションはヘルパーメソッドを使用してforループ内の現在のインデックスに対するインデックス0の合計を取得し、別のソリューションは同じ現在のインデックスからのすべての要素の合計を取得できます。終わり、それはうまくいきます。ここで、要素を配列に入れて合計を比較する場合は、最初に、両側の合計が等しい流出をマークするポイント（インデックス）を見つけ、次にリストを取得して、そのインデックスの前に値を追加し、別のリストを追加しますそのインデックスの後。
これが私のもの（再帰）です。これは、一方の数の合計がもう一方の数の合計と等しくなるように配列を分割する場所があるかどうかを判断するだけです。再帰で簡単に発生する可能性のあるindexOutOfBoundsについて心配すると、わずかなミスが致命的であり、多くの例外やエラーが発生する可能性があります。
public boolean canBalance(int[] nums) {
return (nums.length <= 1) ? false : canBalanceRecur(nums, 0);
}
public boolean canBalanceRecur(int[] nums, int index){ //recursive version
if(index == nums.length - 1 && recurSumBeforeIndex(nums, 0, index)
!= sumAfterIndex(nums, index)){ //if we get here and its still bad
return false;
}
if(recurSumBeforeIndex(nums, 0, index + 1) == sumAfterIndex(nums, index + 1)){
return true;
}
return canBalanceRecur(nums, index + 1); //move the index up
}
public int recurSumBeforeIndex(int[] nums, int start, int index){
return (start == index - 1 && start < nums.length)
? nums[start]
: nums[start] + recurSumBeforeIndex(nums, start + 1, index);
}
public int sumAfterIndex(int[] nums, int startIndex){
return (startIndex == nums.length - 1)
? nums[nums.length - 1]
: nums[startIndex] + sumAfterIndex(nums, startIndex + 1);
}
ここで解決策が見つかりました
package sort;
import java.util.ArrayList;
import java.util.List;
public class ArraySumSplit {
public static void main (String[] args) throws Exception {
int arr[] = {1 , 2 , 3 , 4 , 5 , 5, 1, 1, 3, 2, 1};
split(arr);
}
static void split(int[] array) throws Exception {
int sum = 0;
for(int n : array) sum += n;
if(sum % 2 == 1) throw new Exception(); //impossible to split evenly
List<Integer> firstPart = new ArrayList<Integer>();
List<Integer> secondPart = new ArrayList<Integer>();
if(!dfs(0, sum / 2, array, firstPart, secondPart)) throw new Exception(); // impossible to split evenly;
//firstPart and secondPart have the grouped elements, print or return them if necessary.
System.out.print(firstPart.toString());
int sum1 = 0;
for (Integer val : firstPart) {
sum1 += val;
}
System.out.println(" = " + sum1);
System.out.print(secondPart.toString());
int sum2 = 0;
for (Integer val : secondPart) {
sum2 += val;
}
System.out.println(" = " + sum2);
}
static boolean dfs(int i, int limit, int[] array, List<Integer> firstPart, List<Integer> secondPart) {
if( limit == 0) {
for(int j = i; j < array.length; j++) {
secondPart.add(array[j]);
}
return true;
}
if(limit < 0 || i == array.length) {
return false;
}
firstPart.add(array[i]);
if(dfs(i + 1, limit - array[i], array, firstPart, secondPart)) return true;
firstPart.remove(firstPart.size() - 1);
secondPart.add(array[i]);
if(dfs(i + 1, limit, array, firstPart, secondPart)) return true;
secondPart.remove(secondPart.size() - 1);
return false;
}
}
Python3 solution:
def can_partition(a):
mylist1 = []
mylist2 = []
sum1 = 0
sum2 = 0
for items in a:
# Take total and divide by 2.
total = sum(a)
if total % 2 == 0:
half = total//2
else:
return("Exiting, sum has fractions, total %s half %s" % (total, total/2))
mylist1.append(items)
print('Total is %s and half is %s' %(total, total/2))
for i in a:
sum1 = sum(mylist1)
sum2 = sum(mylist2)
if sum2 < half:
mypop = mylist1.pop(0)
mylist2.append(mypop)
# Function to swtich numbers between the lists if sums are uneven.
def switchNumbers(list1, list2,switch_diff):
for val in list1:
if val == switch_diff:
val_index = list1.index(val)
new_pop = list1.pop(val_index)
list2.append(new_pop)
#Count so while do not get out of hand
count = len(a)
while count != 0:
sum1 = sum(mylist1)
sum2 = sum(mylist2)
if sum1 > sum2:
diff = sum1 -half
switchNumbers(mylist1, mylist2, diff)
count -= 1
elif sum2 > sum1:
diff = sum2 - half
switchNumbers(mylist2, mylist1, diff)
count -= 1
else:
if sum1 == sum2:
print('Values of half, sum1, sum2 are:',half, sum1,sum2)
break
count -= 1
return (mylist1, mylist2)
b = [ 2, 3, 4, 2, 3, 1, 2, 5, 4, 4, 2, 2, 3, 3, 2 ]
can_partition(b)
Output:
Total is 42 total, half is 21.0
Values of half, sum1 & sum2 are : 21 21 21
([4, 4, 2, 2, 3, 3, 2, 1], [2, 3, 4, 2, 3, 2, 5])
def listSegmentation(theList):
newList = [[],[]]
print(theList)
wt1 = 0
wt2 = 0
dWt = 0
for idx in range(len(theList)):
wt = theList[idx]
if (wt > (wt1 + wt2) and wt1 > 0 and wt2 > 0):
newList[0] = newList[0] + newList[1]
newList[1] = []
newList[1].append(wt)
wt1 += wt2
wt2 = wt
elif ((wt2 + wt) >= (wt1 + wt)):
wt1 += wt
newList[0].append(wt)
elif ((wt2 + wt) < (wt1 + wt)):
wt2 += wt
newList[1].append(wt)
#Balancing
if(wt1 > wt2):
wtDiff = sum(newList[0]) - sum(newList[1])
ls1 = list(filter(lambda x: x <= wtDiff, newList[0]))
ls2 = list(filter(lambda x: x <= (wtDiff/2) , newList[1]))
while len(ls1) > 0 or len(ls2) > 0:
if len(ls1) > 0:
elDif1 = max(ls1)
newList[0].remove(elDif1)
newList[1].append(elDif1)
if len(ls2) > 0:
elDif2 = max(ls2)
newList[0].append(elDif2)
newList[1].remove(elDif2)
wtDiff = sum(newList[0]) - sum(newList[1])
ls1 = list(filter(lambda x: x <= wtDiff, newList[0]))
ls2 = list(filter(lambda x: x <= (wtDiff/2) , newList[1]))
if(wt2 > wt1):
wtDiff = sum(newList[1]) - sum(newList[0])
ls2 = list(filter(lambda x: x <= wtDiff, newList[1]))
ls1 = list(filter(lambda x: x <= (wtDiff/2) , newList[0]))
while len(ls1) > 0 or len(ls2) > 0:
if len(ls1) > 0:
elDif1 = max(ls1)
newList[0].remove(elDif1)
newList[1].append(elDif1)
if len(ls2) > 0:
elDif2 = max(ls2)
newList[0].append(elDif2)
newList[1].remove(elDif2)
wtDiff = sum(newList[1]) - sum(newList[0])
ls2 = list(filter(lambda x: x <= wtDiff, newList[1]))
ls1 = list(filter(lambda x: x <= (wtDiff/2) , newList[0]))
print(ls1, ls2)
print(sum(newList[0]),sum(newList[1]))
return newList
#Test cases
lst1 = [4,9,8,3,11,6,13,7,2,25,28,60,19,196]
lst2 = [7,16,5,11,4,9,15,2,1,13]
lst3 = [8,17,14,9,3,5,19,11,4,6,2]
print(listSegmentation(lst1))
print(listSegmentation(lst2))
print(listSegmentation(lst3))
Pythonの非最適なソリューション、
from itertools import permutations
def get_splitted_array(a):
for perm in permutations(a):
l1 = len(perm)
for i in range(1, l1):
if sum(perm[0:i]) == sum(perm[i:l1]):
return perm[0:i], perm[i:l1]
>>> a = [6,1,3,8]
>>> get_splitted_array(a)
((6, 3), (1, 8))
>>> a = [5,9,20,1,5]
>>>
>>> get_splitted_array(a)
((5, 9, 1, 5), (20,))
>>>
そのO（n）時間とO（n）空間
def equal_subarr(arr):
n=len(arr)
post_sum = [0] * (n- 1) + [arr[-1]]
for i in range(n - 2, -1, -1):
post_sum[i] = arr[i] + post_sum[i + 1]
prefix_sum = [arr[0]] + [0] * (n - 1)
for i in range(1, n):
prefix_sum[i] = prefix_sum[i - 1] + arr[i]
for i in range(n - 1):
if prefix_sum[i] == post_sum[i + 1]:
return [arr[:i+1],arr[i+1:]]
return -1
arr=[10, 20 , 30 , 5 , 40 , 50 , 40 , 15]
print(equal_subarr(arr))
>>> [[10, 20, 30, 5, 40], [50, 40, 15]]
arr=[10, 20, 30, 5, 40, 50, 40, 10]
print(equal_subarr(arr))
>>> -1
まず、要素が整数の場合、合計が2で割り切れるのを確認します。それが成功しない場合は不可能です。
私は問題を二分木として設定し、レベル0がどのセット要素0に入るかを決定し、レベル1がどのセット要素1に入るかを決定します。1つのセットの合計が合計の半分であれば、いつでもあなたはやり直し-成功。1つのセットの合計が合計の半分を超える場合はいつでも、そのサブツリーは障害であり、バックアップする必要があります。その時点で、それはツリートラバーサルの問題です。
この問題を解決するための悪い欲張りヒューリスティック：リストを最小から最大にソートし、list1 =奇数要素、list2 =偶数要素として、そのリストを2つに分割してみてください。
public class Problem1 {
public static void main(String[] args) throws IOException{
Scanner scanner=new Scanner(System.in);
ArrayList<Integer> array=new ArrayList<Integer>();
int cases;
System.out.println("Enter the test cases");
cases=scanner.nextInt();
for(int i=0;i<cases;i++){
int size;
size=scanner.nextInt();
System.out.println("Enter the Initial array size : ");
for(int j=0;j<size;j++){
System.out.println("Enter elements in the array");
int element;
element=scanner.nextInt();
array.add(element);
}
}
if(validate(array)){
System.out.println("Array can be Partitioned");}
else{
System.out.println("Error");}
}
public static boolean validate(ArrayList<Integer> array){
boolean flag=false;
Collections.sort(array);
System.out.println(array);
int index=array.size();
ArrayList<Integer> sub1=new ArrayList<Integer>();
ArrayList<Integer> sub2=new ArrayList<Integer>();
sub1.add(array.get(index-1));
array.remove(index-1);
index=array.size();
sub2.add(array.get(index-1));
array.remove(index-1);
while(!array.isEmpty()){
if(compareSum(sub1,sub2)){
index=array.size();
sub2.add(array.get(index-1));
array.remove(index-1);
}
else{
index=array.size();
sub1.add(array.get(index-1));
array.remove(index-1);
}
}
if(sumOfArray(sub1).equals(sumOfArray(sub2)))
flag=true;
else
flag=false;
return flag;
}
public static Integer sumOfArray(ArrayList<Integer> array){
Iterator<Integer> it=array.iterator();
Integer sum=0;
while(it.hasNext()){
sum +=it.next();
}
return sum;
}
public static boolean compareSum(ArrayList<Integer> sub1,ArrayList<Integer> sub2){
boolean flag=false;
int sum1=sumOfArray(sub1);
int sum2=sumOfArray(sub2);
if(sum1>sum2)
flag=true;
else
flag=false;
return flag;
}
}
//欲張りアプローチ//
私はインタビューでこの質問をされました、そして私は以前にどのウェブサイトでもこの問題を見たことがなかったので、私は以下の簡単な解決策を与えました。
配列A={45,10,10,10,10,5}とすると、分割はインデックス= 1（0ベースのインデックス）になり、2つの等しい合計セット{45}と{10,10が得られます。 、10,10,5}
int leftSum = A[0], rightSum = A[A.length - 1];
int currentLeftIndex = 0; currentRightIndex = A.length - 1
/ * currentRightIndex！= currentLeftIndexになるまで、2つのインデックスポインタを配列の中央に向かって移動します。左側の要素の合計が「rightIndex」の右側の要素の合計以下である場合は、leftIndexを増やします。最後に、leftSum==rightSumかどうかを確認します。trueの場合、インデックスはcurrentLeftIndex + 1（または、currentRightIndexはcurrentLeftIndex + 1に等しいため、単にcurrentRightIndex）として取得されます。* /
while (currentLeftIndex < currentRightIndex)
{
if ( currentLeftIndex+1 != currentRightIndex && (leftSum + A[currentLeftIndex + 1) <=currentRightSum )
{
currentLeftIndex ++;
leftSum = leftSum + A[currentLeftIndex];
}
if ( currentRightIndex - 1 != currentLeftIndex && (rightSum + A[currentRightIndex - 1] <= currentLeftSum)
{
currentRightIndex --;
rightSum = rightSum + A[currentRightIndex];
}
}
if (CurrentLeftIndex == currentRightIndex - 1 && leftSum == rightSum)
PRINT("got split point at index "+currentRightIndex);
アルゴリズム：
ステップ1）配列を2つに分割します
ステップ2）合計が等しい場合、分割は完了します
ステップ3）4つのルールに従って、array1の1つの要素をarray2と交換します：
array1の要素の合計が要素の合計よりも小さい場合配列2の
ルール1：
これらの要素の交換が予想される合計を超えて配列1の合計を増加させないように、配列2の数よりも小さい配列1の数を見つけます。見つかった場合は、要素を交換して戻ります。
ルール2：
Rule1が満たされない場合は、array1とarray2の任意の2つの数値の差が、これら2つの数値の差よりも小さくならないように、array2の数値よりも大きいarray1の数値を見つけます。
ELSE
Rule3：
これらの要素を交換し、array1の合計が予想される合計を超えないように、array2の数よりも大きい数をarray1で見つけます。
見つかった場合は、要素を交換して戻ります。
Rule4：
Rule3が満たされない場合は、array1とarray2の任意の2つの数値の差が、これら2つの数値の差よりも小さくならないように、array2の数値よりも小さいarray1の数値を見つけます。
ステップ5）スワップの結果、同じ要素のセットがすでに検出されている配列になるまで、ステップ2に進みます。Setp6）繰り返しが発生した場合、この配列を同じ合計で2つに分割することはできません。現在の配列のセット、またはこの繰り返しの直前に形成されたセットは、配列の最良の分割である必要があります。
注：採用されたアプローチは、結果の合計が期待される合計にできるだけ近くなるように、ある配列から別の配列に要素を交換することです。
Javaプログラムは、Javaコードで入手できます。
package PACKAGE1;
import java.io.*;
import java.util.Arrays;
public class programToSplitAnArray {
public static void main(String args[]) throws NumberFormatException,
IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("enter the no. of elements to enter");
int n = Integer.parseInt(br.readLine());
int x[] = new int[n];
int half;
for (int i = 0; i < n; i++) {
x[i] = Integer.parseInt(br.readLine());
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum = sum + x[i];
}
if (sum % 2 != 0) {
System.out.println("the sum is odd and cannot be divided");
System.out.println("The sum is " + sum);
}
else {
boolean div = false;
half = sum / 2;
int sum1 = 0;
for (int i = 0; i < n; i++) {
sum1 = sum1 + x[i];
if (sum1 == half) {
System.out.println("array can be divided");
div = true;
break;
}
}
if (div == true) {
int t = 0;
int[] array1 = new int[n];
int count = 0;
for (int i = 0; i < n; i++) {
t = t + x[i];
if (t <= half) {
array1[i] = x[i];
count++;
}
}
array1 = Arrays.copyOf(array1, count);
int array2[] = new int[n - count];
int k = 0;
for (int i = count; i < n; i++) {
array2[k] = x[i];
k++;
}
System.out.println("The first array is ");
for (int m : array1) {
System.out.println(m);
}
System.out.println("The second array is ");
for (int m : array2) {
System.out.println(m);
}
} else {
System.out.println("array cannot be divided");
}
}
}
}
これを試してみて、機能しない場合はお知らせください。それがあなたを助けることを願っています。
static ArrayList<Integer> array = null;
public static void main(String[] args) throws IOException {
ArrayList<Integer> inputArray = getinputArray();
System.out.println("inputArray is " + inputArray);
Collections.sort(inputArray);
int totalSum = 0;
Iterator<Integer> inputArrayIterator = inputArray.iterator();
while (inputArrayIterator.hasNext()) {
totalSum = totalSum + inputArrayIterator.next();
}
if (totalSum % 2 != 0) {
System.out.println("Not Possible");
return;
}
int leftSum = inputArray.get(0);
int rightSum = inputArray.get(inputArray.size() - 1);
int currentLeftIndex = 0;
int currentRightIndex = inputArray.size() - 1;
while (leftSum <= (totalSum / 2)) {
if ((currentLeftIndex + 1 != currentRightIndex)
&& leftSum != (totalSum / 2)) {
currentLeftIndex++;
leftSum = leftSum + inputArray.get(currentLeftIndex);
} else
break;
}
if (leftSum == (totalSum / 2)) {
ArrayList<Integer> splitleft = new ArrayList<Integer>();
ArrayList<Integer> splitright = new ArrayList<Integer>();
for (int i = 0; i <= currentLeftIndex; i++) {
splitleft.add(inputArray.get(i));
}
for (int i = currentLeftIndex + 1; i < inputArray.size(); i++) {
splitright.add(inputArray.get(i));
}
System.out.println("splitleft is :" + splitleft);
System.out.println("splitright is :" + splitright);
}
else
System.out.println("Not possible");
}
public static ArrayList<Integer> getinputArray() {
Scanner scanner = new Scanner(System.in);
array = new ArrayList<Integer>();
int size;
System.out.println("Enter the Initial array size : ");
size = scanner.nextInt();
System.out.println("Enter elements in the array");
for (int j = 0; j < size; j++) {
int element;
element = scanner.nextInt();
array.add(element);
}
return array;
}
}
public boolean splitBetween(int[] x){
int sum=0;
int sum1=0;
if (x.length==1){
System.out.println("Not a valid value");
}
for (int i=0;i<x.length;i++){
sum=sum+x[i];
System.out.println(sum);
for (int j=i+1;j<x.length;j++){
sum1=sum1+x[j];
System.out.println("SUm1:"+sum1);
}
if(sum==sum1){
System.out.println("split possible");
System.out.println("Sum: " +sum +" Sum1:" + sum1);
return true;
}else{
System.out.println("Split not possible");
}
sum1=0;
}
return false;
}
再帰を伴う非常に単純なソリューション
public boolean splitArray(int[] nums){
return arrCheck(0, nums, 0);
}
public boolean arrCheck(int start, int[] nums, int tot){
if(start >= nums.length) return tot == 0;
if(arrCheck(start+1, nums, tot+nums[start])) return true;
if(arrCheck(start+1, nums, tot-nums[start])) return true;
return false;
}
https://github.com/ShubhamAgrahari/DRjj/blob/master/Subarray_Sum.java
パッケージソリューション;java.util.Scannerをインポートします。
パブリッククラスソリューション{
static int SplitPoint(int arr[], int n) { int leftSum = 0; for (int i = 0 ; i < n ; i++) leftSum += arr[i]; int rightSum = 0; for (int i = n-1; i >= 0; i--) { rightSum += arr[i]; leftSum -= arr[i] ; if (rightSum == leftSum) return i ; } return -1; } static void output(int arr[], int n) { int s = SplitPoint(arr, n); if (s == -1 || s == n ) { System.out.println("Not Possible" ); return; } for (int i = 0; i < n; i++) { if(s == i) System.out.println(); System.out.print(arr[i] + " "); } } public static void main (String[] args) { Scanner sc= new Scanner(System.in); System.out.println("Enter Array Size"); int n = sc.nextInt(); int arr[]= new int[n]; for(int i=0;i<n;i++) { arr[i]=sc.nextInt(); } output(arr, n); } }