用C子集和遞歸++

Question

這是獲得真實的或給定和目標值

bool subsetSumExists(Set<int> & set, int target) { 
    if (set.isEmpty()) { 
     return target == 0; 
    } else { 
     int element = set.first(); 
     Set<int> rest = set - element; 
     return subsetSumExists(rest, target) 
     || (subsetSumExists(rest, target- element)); 
    } 
} 

假然而，這種解決方案將只返回true或false值的解決方案之一。如何獲得涉及子集的元素（集合在一起的集合將等於目標）？

我必須使用動態編程嗎？因爲我知道..遞歸實際上是建立堆棧，並且在函數返回值之後，框架內的值也將被丟棄。

那麼，是否有可能獲得加起來等於目標值的元素。

傳遞一個對象的問題的解決方案？

謝謝

Answer 1

首先，你可以優化你的程序一點點 - 檢查目標是0，如果它總是返回true。現在你需要的是在某個地方存儲你已經使用過的元素。我將向您展示一種方法，使用全局「堆棧」（實際上是vector，以便您可以迭代它），因爲這樣代碼將更易於理解，但您也可以通過引用該函數來傳遞它，或者避免以其他方式使其成爲全球性的。 順便說一下，stl容器被調用set而不是Set。

vector<int> used; 
bool subsetSumExists(Set<int> & set, int target) { 
    if (target == 0) { 
     cout << "One possible sum is:\n"; 
     for (int i = 0; i < used.size(); ++i) { 
      cout << used[i] << endl; 
     } 
     return true; 
    } else if(set.empty()) { 
     return false; 
    }else { 
     int element = set.first(); 
     Set<int> rest = set - element; 
     used.push_back(element); 
     if (subsetSumExists(rest, target- element)) { 
      return true; 
     } else { 
      used.pop_back(); 
     } 
     return subsetSumExists(rest, target); 
    } 
} 

希望這會有所幫助。