從數字數組中找到所有加法和減法組合

我需要創建一個函數來獲取數字和目標數字的數組，並返回可以添加或減去這些數字以獲得目標數字的多種不同方法。從數字數組中找到所有加法和減法組合

即。

值= 2，4，6，8目標= 12

2 + 4 + 6 = 12，

4 + 8 = 12，

6 + 8 - 2 = 12，

2 - 4 + 6 + 8 = 12，

返回4

這裏是我迄今爲止，但它只有c計入附加問題。

private void RecursiveSolve(int goal, int currentSum, List<int> included, List<int> notIncluded, int startIndex) 
{ 
    for (int index = startIndex; index < notIncluded.Count; index++) 
    { 
     int nextValue = notIncluded[index]; 
     if (currentSum + nextValue == goal) 
     { 
      List<int> newResult = new List<int>(included); 
      newResult.Add(nextValue); 
      mResults.Add(newResult); 
     } 
     else if (currentSum - nextValue == goal) 
     { 
      List<int> newResult = new List<int>(included); 
      newResult.Add(nextValue); 
      mResults.Add(newResult); 
     } 

     if (currentSum - nextValue < goal && currentSum - nextValue > 0) 
     { 
      List<int> nextIncluded = new List<int>(included); 
      nextIncluded.Add(nextValue); 
      List<int> nextNotIncluded = new List<int>(notIncluded); 
      nextNotIncluded.Remove(nextValue); 
      RecursiveSolve(goal, currentSum - nextValue, nextIncluded, nextNotIncluded, startIndex++); 
     } 

     if (currentSum + nextValue < goal) 
     { 
      List<int> nextIncluded = new List<int>(included); 
      nextIncluded.Add(nextValue); 
      List<int> nextNotIncluded = new List<int>(notIncluded); 
      nextNotIncluded.Remove(nextValue); 
      RecursiveSolve(goal, currentSum + nextValue, nextIncluded, nextNotIncluded, startIndex++); 
     } 
    } 
}

來源

2012-06-08 Timothy Massing

你不能通過將列表{2,4,6}改爲{2,4,6，-2，-4，-6}來處理減法嗎？ –

這是一個有趣的想法。我會研究一下。 –

那麼，簡單的方法是嘗試所有的組合。如果你有N個號碼，你有3^N個組合。推理是這樣的：你總結數字，但在他們每個人面前放上一個係數。如果您的號碼是A1..AN，增加N個係數（C1..CN）和金額：

Sum (Ai*Ci)

你順可以是1（這意味着你加號），-1（這意味着你減去的數）或0（意味着你忽略了這個數字）。

因此，將所有3^N個可能的係數賦值，計算總和並與您的目標進行比較。

我假設所有的數字是不同的（如在你的例子）。如果一個數字可以出現兩次，您需要考慮這一點。

來源

2012-06-08 06:13:05 zmbq

從數字數組中找到所有加法和減法組合

回答

相關問題