查找數組中的所有數字組合，加起來輸入數字

嘿，我正在研究一個算法，它需要用戶輸入的數字，然後通過一個大小爲50的數組，填充1到100之間的隨機數並找到加起來到輸入數字的所有數字組合。例如，給定一個整數數組[3,6,1,9,2,5,12]並傳遞整數值9，您將返回[[3,6]，[6,1，...， 2]，[9]，[3,1,5]。在數組中返回結果的順序並不重要，儘管你應該返回唯一的集合（即[6,3]和[3,6]是相同的，只有一個應該返回）。此外，單個結果應該按照它們發現的順序排列（即[6,1,2]應該返回，而不是[1,2,6]）。查找數組中的所有數字組合，加起來輸入數字

當我開始編寫代碼時，我遇到的第一個解決方案似乎非常無效。我目前正試圖將每個組合分成它自己的數組，並且每次將數字添加到數組時，都會執行檢查以查看數字是否等於輸入，仍然小於或超過它。它不能正常工作，我覺得這可能是一種低效的方式：

for (int i = 0; i < list.length; i++) { 
     List<Integer> combo = new ArrayList<Integer>(); 
     int counter = 0; 
     int current = list[i]; 
     if (current == input){ 
     System.out.println(i); 
     } 
     else if (current > input) { 
     continue; 
     } 
     else if (current < input) { 
     combo.add(current); 
     if (combo.size() >= 2) { 
      for (int j = 0; j < combo.size(); j++) { 
      counter += combo.get(j); 
      if (counter == input) { 
       System.out.println("Success"); 
       break; 
      } 
      else if (counter < input) { 
       continue; 
      } 
      else if (counter > input) { 
       break; 
      }     
      } 
     } 
     } 
    }

來源

2016-08-20 Spance

如果我們應該忽略代碼的某些部分，爲什麼包括這些部分呢？不是說它是不可讀的，但這仍然是不必要的 – Dici

當然，我繼續並將它們取出 – Spance

該算法必須是低效率的，因爲它是Subset Sum問題的變體：https：//en.wikipedia.org/wiki/Subset_sum_problem – mszymborski

這是一個想法，我沒有一個工作代碼。嘗試使用遞歸，測試所有組合的最大可能數量加上所有其餘的沒有它。函數如：Sums（Number，maxN），（maxN是我們可以使用的最大數字 - 在第一次調用時爲9）對於您的示例應該是：
1.按照建議對它們進行排序並剪切大於輸入。
2.檢查maxN是否大於求和所需的最小值，在你的例子中它是5（不能使9中的數字小於5）。如果不是返回（基本情況）。
3.是否maxN等於tu輸入？（第一次通話中有9個）
a）是 - 第一個解決方案子集[9] +和（數量，dec（maxN））（dec（maxN）將在第一次通話中爲6）
b）否 - 遞歸檢查'數量 - maxN'可以從你的集合中的數字來構建，Sums（Number - maxN，dec（K）或者'Number - maxN'的最大數量（取決於哪個更小））+ Sums（Number，dec（maxN）） - 添加其餘的。

這裏是代碼只算，方法寫一個數字作爲平方和，它通過HackerRank測試：

import math 
def minArgument(x): 
    s = 0 
    i = 1 
    while s < x: 
     s = s + i * i 
     i = i + 1 
    return i - 1 
def maxPower(a): 
    return math.floor(math.sqrt(a)) 
def sumOfSquares(M, K, cnt): 
    if M < 1: 
     return cnt 
lowerLimit = minArgument(M) 
    if K < lowerLimit: 
     return cnt 
    else: 
     if K * K == M: 
     return sumOfSquares(M, K - 1, cnt + 1) 
    else: 
     return sumOfSquares(M, K - 1,sumOfSquares(M - K * K, 
        min(maxPower(M - K * K), K - 1), cnt))

輕易地變更後，這給你的解決方案的數量。我不明白如何建立一個組合列表作爲返回值現在...

來源

2016-08-21 01:02:20

查找數組中的所有數字組合，加起來輸入數字

回答

相關問題