打印所有子集是總結到特定值

Question

我是想有一段時間來找到所有元素^{（包括非連續）數組，總計達到特定值的}：

using System; 

namespace ProgrammingBasics 
{ 
    class Exercise 
    { 
     static void Main() 
     { 
      PrintArray(arr); 
      SubarrayWithSum(); 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Data members. 

     */ 
     // targer array 
     static int[] arr = { 2, 1, 2, 4, 3, 5, 2, 6 }; 
     // target sum 
     static int sum = 14; 

     //-------------------------------------------------------------------- 

     /* 
      Method: IsSubarrayWithSum(arr, sum); 

      It returns a bool value that indicates 
      whether there is a subarray within arr 
      with elements that sum up to specific value. 
     */ 
     static void SubarrayWithSum() 
     { 
      int depth = 0; 
      int startIndex = 0; 
      int endIndex = 1; 

      CheckAllCombinations(new int[arr.Length], startIndex, endIndex, depth); 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Method: CheckAllCombinations(subarray, sum); 

     */ 
     static void CheckAllCombinations(int[] subarray, int startIndex, int endIndex, int depth) 
     { 
      if (depth >= arr.Length) 
      { 
       return; 
      } 
      //Console.ReadKey(); 
      for (int i = startIndex; i < endIndex; i++) 
      { 
       subarray[i] = arr[i]; 
       //Console.WriteLine("startIndex = {0}, depth = {1}, i = {2}", startIndex, depth, i); 
       if (IsWantedSum(subarray)) 
       { 
        Console.Write("S = {0} -> yes", sum); 
        PrintSubArray(subarray); 
       } 
       //PrintArray(subarray); 
       //Console.ReadKey(); 
       CheckAllCombinations(new int [arr.Length], startIndex += 1, endIndex = (endIndex < arr.Length)? endIndex + 1 : endIndex, depth += 1); 
      } 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Method: IsWantedSum(int[] arr) 

     */ 
     static bool IsWantedSum(int[] arr) 
     { 
      int currentSum = 0; 

      for (int i = 0; i < arr.Length; i++) 
      { 
       currentSum += arr[i]; 
      } 

      if (currentSum == sum) 
      { 
       return true; 
      } 
      else 
      { 
       return false; 
      } 
     } 

     //-------------------------------------------------------------------- 
     /* 
      Method: PrintArray(); 

     */ 
     static void PrintArray(int[] subarray) 
     { 
      Console.Write("{"); 
      for (int i = 0; i < subarray.Length; i++) 
      { 
       Console.Write(subarray[i]); 
       if (i < subarray.Length -1) Console.Write(", "); 
      } 
      Console.WriteLine("}"); 
     } 

     //-------------------------------------------------------------------- 
     /* 
      Method: PrintSubArray(); 

     */ 
     static void PrintSubArray(int[] subarray) 
     { 
      Console.Write("("); 
      for (int i = 0; i < subarray.Length; i++) 
      { 
       if (subarray[i] != 0)Console.Write(subarray[i]); 
       if (subarray[i] != 0 && i < subarray.Length - 1) Console.Write(" + "); 
      } 
      Console.WriteLine(" = {0})", sum); 
     } 
    } 
} 

我得到有些部分正確的結果：

{2，1，2，4，3，5，2，6}
S = 14 - >是（4 + 3 + 5 + 2 + = 14）
S = 14→是（2 + 4 + 3 + 5 + = 14）（4 + 3 + 5 + 2 + = 14）
S = 14→是（2） + 4 + 3 + 5 + = 14）
S = 14 - >是（4 + 3 + 5 + 2 + = 14）

與重複和缺失的非連續的元件，諸如的子陣列：

是（1 + 2 + 5 + 6 = 14）

有人可以給我一個關於我的算法問題的提示，並可能提出一個更正/新的實現？

Answer 1

OK，這裏是小嚐試簡要介紹一下，我經歷來理解問題和實現基本的解決方案的信息。

事實證明，The Subset Sum Problem被認爲是Knapsack Problem的特殊情況，我們正在尋找最大化利潤而所謂的保值根據具體能力重量，但在我們的情況下，利潤和重量與每個值相關的是相同的。

有各種「揹包問題」描述偉大的解決方案 - 凱勒，Pferschy，Pisinger，不過，暫且最簡單的解決方案，我可以實現和理解，而不是攜帶的複雜性和/或療效，看起來是這樣的：

//-------------------------------------------------------------------- 

    /* 
     Method: FindSubArray(); 

     Base case: - if current sum == targer sum: print current elements. 
        - if index == arr.Length: terminate search. 

     Recursive step: 
        - do not/select element with index and do not/update the current sum; recursive call with updated current sum and index. 
    */ 
    static void FindSubArray(int index, int currentSum, bool[] subArray) 
    { 
     // base case 
     if (currentSum == targetSum) 
     { 
      PrintSubArray(subArray); 
     } 
     else if (index == arr.Length) 
     { 
      return; 
     } 
     else 
     { 
      // recursive calls 
      subArray[index] = true; 
      currentSum += arr[index]; 
      FindSubArray(index + 1, currentSum, subArray); 

      currentSum -= arr[index]; // restore previous value of the sum signifying: element not selected 
      subArray[index] = false; 
      FindSubArray(index + 1, currentSum, subArray); 
     } 
    } 

其中PrintSubArray(subArray);打印所有的arr的元素subArray打上true。

輸出：

{2，1，2，4，3，5，2，6}
S = 14 - >是（2 + 1 + 2 + 4 + 3 + 2 + （2 + 1 + 2 + 3 + 6 = 14）
S = 14） （2 + 1 + 3 + 2 + 6 = 14）
S = 14 - >是（2 + 1 + 4 + 5 + 1 + 5 + 6 = 14）
S = 14→是（2 + 2 + 4 + 6 = 14）
S = 14→是（2 + 4 + 3 + 5 + = 14）
S = 14→是（2 + 4 + 2 + 6 = 14）
S = 14→是（1 + 2 + 4 + 5 + 2 + = 14）
S = 14→是（1 + 2 + 3 + 2 + 6 = 14）
S = 14→是（1 + 2 + 5 + 6 = 14）
S = 14→是（2 + 4 + 3 + 5 + = 14）
S = 14 - >是（2 + 4 + 2 + 6 = 14）
S = 14 - >是（4 + 3 + 5 + 2 + = 14）
S = 14 - >是（3 + 5 + 6 = 14）

---

1. 說我只是閱讀狀態的問題，因爲這本書：「查找是否存在與元素的子陣列總結到特定值」。

Answer 2

這裏有一個簡單的方法來完成它的組合。可能有更好的方法來存儲它們（我正在考慮使用字典來編碼您已有的所有子款項）。在一天結束時，如果你想要考慮非連續的元素，你將不得不在這種情況下獲得可能的子數組，而不只是看連續的選擇。對組合算法的信用轉到ojlovecd here。

class Exercise 
    { 
     static void Main() 
     { 
      PrintArray(arr); 
      // SubarrayWithSum(); 


      var result = GetCombination(arr); 

      foreach(var list in result) 
      { 
       var total = list.Sum(); 
       if (total == sum) 
        PrintArray(list); 
      } 
     } 
     static List<int> arr = new List<int> { 2, 1, 2, 4, 3, 5, 2, 6 }; 
     static int sum = 14; 

     static List<List<int>> GetCombination(List<int> list) 
     { 
      var result = new List<List<int>>(); 
      result.Add(new List<int>()); 
      double count = Math.Pow(2, list.Count); 
      for (int i = 1; i <= count - 1; i++) 
      { 
       string str = Convert.ToString(i, 2).PadLeft(list.Count, '0'); 
       for (int j = 0; j < str.Length; j++) 
       { 
        if (str[j] == '1') 
        { 
         result[i - 1].Add(list[j]); 
        } 
       } 
       result.Add(new List<int>()); 
      } 
      return result; 
     } 

     static void PrintArray(List<int> subarray) 
     { 
      Console.Write("{"); 
      for (int i = 0; i < subarray.Count; i++) 
      { 
       Console.Write(subarray[i]); 
       if (i < subarray.Count - 1) Console.Write(", "); 
      } 
      Console.WriteLine("}"); 
     } 
    } 

Answer 3

我想重複的發生是因爲你在數組中添加了零。查看更快運行的更新代碼。

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Text.RegularExpressions; 

namespace ProgrammingBasics 
{ 
    class Exercise 
    { 
     static void Main() 
     { 
      PrintArray(arr); 
      SubarrayWithSum(); 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Data members. 

     */ 
     // targer array 
     static int[] arr = { 2, 1, 2, 4, 3, 5, 2, 6 }; 
     // target sum 
     static int sum = 14; 

     //-------------------------------------------------------------------- 

     /* 
      Method: IsSubarrayWithSum(arr, sum); 

      It returns a bool value that indicates 
      whether there is a subarray within arr 
      with elements that sum up to specific value. 
     */ 
     static void SubarrayWithSum() 
     { 
      int depth = 0; 
      int endIndex = arr.Length - 1; 

      CheckAllCombinations(new int[arr.Length], depth); 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Method: CheckAllCombinations(subarray, sum); 

     */ 
     static void CheckAllCombinations(int[] subarray, int depth) 
     { 
      //Console.ReadKey(); 
      for (int i = depth; i < arr.Length; i++) 
      { 
       subarray[depth] = arr[i]; 
       Console.WriteLine("depth = {0}, i = {1}, array = '{2}' ", depth, i, string.Join(",", subarray.Select(x => x.ToString()).ToArray())); 
       int currentSum = subarray.Take(depth + 1).Sum(); 
       if (currentSum == sum) 
       { 
        Console.Write("S = {0} -> yes : ", sum); 
        Console.WriteLine(string.Join(",", subarray.Take(depth + 1))); 
       } 
       //PrintArray(subarray); 
       //Console.ReadKey(); 
       if (currentSum < sum) 
       { 
        CheckAllCombinations(subarray, depth + 1); 
       } 
      } 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Method: IsWantedSum(int[] arr) 

     */ 

     //-------------------------------------------------------------------- 
     /* 
      Method: PrintArray(); 

     */ 
     static void PrintArray(int[] subarray) 
     { 
      Console.Write("{"); 
      for (int i = 0; i < subarray.Length; i++) 
      { 
       Console.Write(subarray[i]); 
       if (i < subarray.Length - 1) Console.Write(", "); 
      } 
      Console.WriteLine("}"); 
     } 

     //-------------------------------------------------------------------- 
     /* 
      Method: PrintSubArray(); 

     */ 
     static void PrintSubArray(int[] subarray) 
     { 
      Console.Write("("); 
      for (int i = 0; i < subarray.Length; i++) 
      { 
       if (subarray[i] != 0) Console.Write(subarray[i]); 
       if (subarray[i] != 0 && i < subarray.Length - 1) Console.Write(" + "); 
      } 
      Console.WriteLine(" = {0})", sum); 
     } 
    } 
}