數組遞歸困惑（java）

-2

給定一個int數組，是否可以將int分成兩組，以便兩組的和是相同的。每個int必須位於一個組中或另一個組中。編寫一個遞歸輔助方法，它接受你喜歡的任何參數，並從splitArray（）對你的遞歸助手進行初始調用。（不需要循環）數組遞歸困惑（java）

這是編碼蝙蝠的一個問題，我試圖弄清楚。我被困住了，所以我找到了一個解決方案，但是我對一行的目的感到困惑，並且完全被最終的return語句所做的事迷惑。謝謝你的幫助！

public boolean splitArray(int[] nums) { 

return splitArrayHelper(nums, 0, new int[nums.length], 0, 0, new int[nums.length], 0, 0); 
} 

private boolean splitArrayHelper(int[] nums, int n, int[] split1, int s1, int t1, int[] split2, int s2, int t2) { 

if (n == nums.length) 
return t1 == t2; //returns true or false 

split2[s2] = split1[s1] = nums[n]; // What is the purpose of this line? 

return 
splitArrayHelper(nums, n + 1, split1, s1 + 1, t1 + nums[n], split2, s2, t2) || 
splitArrayHelper(nums, n + 1, split1, s1, t1, split2, s2 + 1, t2 + nums[n]); 
} //I don't know what this return statement is doing. How is the or statement decided?

來源

2014-06-07 user3713351

的代碼是讓人有些困惑。變量命名不是很清楚。但是，我可以看到算法使用遞歸來解決這個問題。或者「||」在簡單的return語句中或遞歸調用返回的兩個布爾值。 – vda8888

對不起。你對於退貨的解釋並不完全清楚。 – user3713351

的想法是，我們必須將原來的數組拆分成2個數組，稱爲A和B，所以對於原始數組中每一個數字，這個數字將要麼屬於A或B.我們保持A（group1Total）和B（group2Total）之和的總和。

我會寫我的助手像下面

private static boolean splitHelp(int[] nums, int elementCount, int group1Total, int group2Total) { 
      if (elementCount == nums.length) { 
       return group1Total == group2Total; 
      } 

      return splitHelp(nums, elementCount + 1, group1Total+ nums[n], group2Total) //The element belongs to array A 
|| splitHelp(nums, n + 1, group1Total, group2Total+ nums[n]) //or the element belongs to array B; 
     }

來源

2014-06-07 22:58:47 vda8888

如何做出決定？我看到它在第一個數組或第二個數組中，但實際的標準在哪裏？ – user3713351

爲了想象這一點，在每一步中，我們都有一個數字nums [n]和兩個總和：group1Total或group2Total。所以我們有兩種可能：將nums [n]放入group1Total，或將nums [n]放入group2Total。對於每種可能性，我們使用遞歸重複數組中下一個數字的過程（nums [n + 1]）。換句話說，我們嘗試了所有2^n種可能性。 – vda8888

所以這給了我們兩種可能性，直到在if語句中調用最終返回語句爲止？ – user3713351

數組遞歸困惑（java）

回答

相關問題