如何提高算法總和？

Question

考慮的源代碼：

public class subSetSumR { 
    // Solving Subset sum using recursion 
    // Programmed by Fuentes, Feb. 9, 2009 
    // Subset sum consists of finding a subset of mySet whose elements add up to goal 
    // It is a well-known NP-complete problem 

    public static boolean subSetSumRecur (int[] mySet, int n, int goal) { 
     if (goal == 0) return true; 

     if ((goal < 0) | (n >= mySet.length)) return false; 

     if (subSetSumRecur(mySet, n + 1, goal - mySet[n])) { 
      System.out.print(mySet[n] + " "); 
      return true; 
     } 

     if (subSetSumRecur(mySet, n + 1, goal)) return true; 

     return false; 
    } 
} 

重要的事實：輸入的數量大於1我如何利用這一點來加快上述解決方案？

Answer 1

1. 您可以使用memoization來避免重複計算。
2. 您可以使用dp來做更好的事情。 （開始用空的哈希集合，並逐步加入數1 1與陣列成長集）

 
    set = emptyset; 
    for(num : array_of_number) 
    { 
     newset = emptyset; 
     for(item : set) 
     { 
     if(num + item == goal) return ""we found it"; 
     newset.insert(num + item); 
     } 
     set.insert(newset); 
    } 
    return "Not possible"; 

記憶化

set<tuple<int, int>> memo; // Make sure to clear before calling your function 
public static boolean subSetSumRecur (int[] mySet, int n, int goal) { 
    if(set.contains(tuple(n, goal)) return false; 
    set.insert(tuple(n, goal)); 
    ... 
    ... /* Your code goes here */ 
    ... 
} 

在java中應該有類似設置的東西（我認爲hashset）和元組（在C++ std :: pair中是最好的選擇。如果在java中沒有類似的話，你可以創建一個包含2個可插入到hashset中的int類的小類）。