java遞歸：數字的最佳集合

Question

給定一個整數數組並給出另一個整數。如何使用遞歸從該數組中找到一個整數集合，以便集合的總和最接近給定的整數？ 例如，給定數組：1,2,3和給定的整數是5，則方法返回2,3; 另一個例子：如果給定的陣列是：35,14,45,3和給定的整數是50，則該方法返回35和14

Answer 1

它看起來像一個功課，所以我將不把任何代碼，但嘗試解釋算法。 想象一下，你得到[35, 14, 45, 3]和50;

1. First sort the array in descending order: [45, 35, 14, 3] 
    2. You should remove the 1st item in the array and take it or leave it 
    3. So you'll have two smaller problems: 
     [35, 14, 3] and 5 (45 is taken) 
     [35, 14, 3] and 50 (45 is left) 
    4. To cut story short keep the best score so far: 5 in your case. 
    It let you trim some negative value branches 
     [35, 14, 3] and 5 (45 is taken) is the best so far 
    5. If the array is not empty, go to the step 2 

整個軌跡是

[35, 14, 3] and 5 (45 taken) // the best score so far 
     [14, 3] and -30 (45, 35 taken) // trim: worse than the best score so far 
     [14, 3] and 5 (45 taken) 
      [3] and -9 (45, 14 taken) // trim 
      [3] and 5 (45 taken) 
      [] and 2 (45, 3 taken) // the best score so far 
      [] and 5 (45 taken)  
    [35, 14, 3] and 50 (nothing taken) 
     [14, 3] and 15 (35 taken) 
      [3] and 1 (35, 14 taken) // the best score so far 
      [] and -2 (35, 14, 3 taken) 
      [3] and 15 (35 taken) 
      [] and 12 (35, 3 taken) 

     ...   

最後，至今最好的分數1是(35, 14)採取的解決方案。 執行時，您可以做兩個遞歸調用：一個用於「take」和一個用於「離開」。