feat: add Subset Sum (TheAlgorithms#2020)

* Create subset_sum.cpp * Update subset_sum.cpp Lint formatting. * chore: apply suggestions from code review * chore: apply suggestions from code review * fix: CI issues Co-authored-by: David Leal <halfpacho@gmail.com>
ShuN6211 · Jan 24, 2023 · a6a9d8e · a6a9d8e
1 parent f093837
commit a6a9d8e
Showing 1 changed file with 125 additions and 0 deletions.
diff --git a/dynamic_programming/subset_sum.cpp b/dynamic_programming/subset_sum.cpp
@@ -0,0 +1,125 @@
+/**
+ * @file
+ * @brief Implements [Sub-set sum problem]
+ * (https://en.wikipedia.org/wiki/Subset_sum_problem) algorithm, which tells
+ * whether a subset with target sum exists or not.
+ *
+ * @details
+ * In this problem, we use dynamic programming to find if we can pull out a 
+ * subset from an array whose sum is equal to a given target sum. The overall 
+ * time complexity of the problem is O(n * targetSum) where n is the size of 
+ * the array. For example, array = [1, -10, 2, 31, -6], targetSum = -14. 
+ * Output: true => We can pick subset [-10, 2, -6] with sum as 
+ * (-10) + 2 + (-6) = -14.
+ * @author [KillerAV](https://github.com/KillerAV)
+ */
+
+#include <cassert>        /// for std::assert
+#include <iostream>       /// for IO operations
+#include <vector>          /// for std::vector
+#include <unordered_map>   /// for unordered map
+
+/**
+ * @namespace dynamic_programming
+ * @brief Dynamic Programming algorithms
+ */
+namespace dynamic_programming {
+
+/**
+ * @namespace subset_sum
+ * @brief Functions for [Sub-set sum problem]
+ * (https://en.wikipedia.org/wiki/Subset_sum_problem) algorithm
+ */
+namespace subset_sum {
+
+/**
+ * Recursive function using dynamic programming to find if the required sum 
+ * subset exists or not.
+ * @param arr input array
+ * @param targetSum the target sum of the subset
+ * @param dp the map storing the results
+ * @returns true/false based on if the target sum subset exists or not.
+ */
+bool subset_sum_recursion(
+    const std::vector<int> &arr, 
+    int targetSum, 
+    std::vector<std::unordered_map<int, bool>> *dp,
+    int index = 0) {
+
+    if(targetSum == 0) { // Found a valid subset with required sum.
+        return true;
+    }
+    if(index == arr.size()) { // End of array
+        return false;
+    }
+
+    if ((*dp)[index].count(targetSum)) { // Answer already present in map
+        return (*dp)[index][targetSum];
+    }
+
+    bool ans = subset_sum_recursion(arr, targetSum - arr[index], dp, index + 1) 
+      || subset_sum_recursion(arr, targetSum, dp, index + 1);
+    (*dp)[index][targetSum] = ans; // Save ans in dp map.
+    return ans;
+}
+
+/**
+ * Function implementing subset sum algorithm using top-down approach
+ * @param arr input array
+ * @param targetSum the target sum of the subset
+ * @returns true/false based on if the target sum subset exists or not.
+ */
+bool subset_sum_problem(const std::vector<int> &arr, const int targetSum) {
+    size_t n = arr.size();
+    std::vector<std::unordered_map<int, bool>> dp(n);
+    return subset_sum_recursion(arr, targetSum, &dp);
+}
+}  // namespace subset_sum
+}  // namespace dynamic_programming
+
+/**
+ * @brief Test Function
+ * @return void
+ */
+static void test() {
+    // custom input vector
+    std::vector<std::vector<int>> custom_input_arr(3);
+    custom_input_arr[0] = std::vector<int> {1, -10, 2, 31, -6};
+    custom_input_arr[1] = std::vector<int> {2, 3, 4};
+    custom_input_arr[2] = std::vector<int> {0, 1, 0, 1, 0};
+
+    std::vector<int> custom_input_target_sum(3);
+    custom_input_target_sum[0] = -14;
+    custom_input_target_sum[1] = 10;
+    custom_input_target_sum[2] = 2;
+
+    // calculated output vector by pal_part Function
+    std::vector<int> calculated_output(3);
+
+    for (int i = 0; i < 3; i++) {
+        calculated_output[i] =
+            dynamic_programming::subset_sum::subset_sum_problem(
+                custom_input_arr[i], custom_input_target_sum[i]);
+    }
+
+    // expected output vector
+    std::vector<bool> expected_output{true, false, true};
+
+    // Testing implementation via assert function
+    // It will throw error if any of the expected test fails
+    // Else it will give nothing
+    for (int i = 0; i < 3; i++) {
+        assert(expected_output[i] == calculated_output[i]);
+    }
+
+    std::cout << "All tests passed successfully!\n";
+}
+
+/**
+ * @brief Main function
+ * @returns 0 on exit
+ */
+int main() {
+    test();  // execute the test
+    return 0;
+}