如何從給定整數的特定數據中找到所有唯一可能的分區方式

Question

我想讓java程序從給定整數的特定數據（數組列表）中統計出所有可能的唯一方式。

Example : 
 
input: 3 6 
 
     1 2 3 
 
output: 7 
 

 
explanation: the first line contains two separated integers of value x,y. 
 
the second line contains x separated integers 
 

 
For y = 6 and x = {1, 2, 3} there are exactly seven ways:
  
 
1. {1, 1, 1, 1, 1, 1} <— sum up to 6
  
 
2. {1, 1, 1, 1, 2} <- sum up to 6 
 
3. {1, 1, 1, 3} <- sum up to 4 
 
4. {2, 2, 2} <— sum up to 6 
 
5. {2, 2, 1, 1} <— sum up to 6 
 
6. {1, 2, 3} <— sum up to 6 
 
7. {3, 3} <- sum up to 6

Answer 1

你的問題還不清楚，但我想你問的是「計數的方式，加起來y只用一組數字儘可能加數的數量」。

我假設第二行中的數字都是不同的，都小於y（好吧，這並不是真的有必要），並且都是正面的。

一個解決方案是使用遞歸方法。說f(y, {x_1, ..., x_n})是使用x_i的方式加起來的方法數量最多爲y。

然後f(y, {x_1, ..., x_n}) = sum of f(y - x_i, {x_1, ..., x_n}) for i = 1, ..., n。

你現在可以寫一個遞歸函數。基本情況是什麼？那麼，y可能是0，所以答案是1.或y可能是負數，答案是0.

這應該這樣做。但它可能會非常低效。我鼓勵你閱讀遞歸和計算斐波納契數字，以瞭解如何提高效率（提示：記憶，而自下而上的方法而不是自上而下的方法是你的朋友）。