# Subset Sum 系列 (Not on Leetcode)

還有一些題型也屬於這類，但不在 Leetcode 上，記錄一下：

1. Subset Sum

   核心概念，每遇到一個 element 就有要放進 subset or 不放進 subset 兩種選項。

   #include <iostream>
   #include <vector>
   
   using namespace std;
   
   class SubsetSum {
   public:
    bool canPartition(const vector<int> &num, int sum) {
      int n = num.size();
      vector<vector<bool>> dp(n, vector<bool>(sum + 1));
   
      // populate the sum=0 columns, as we can always form '0' sum with an empty set
      for (int i = 0; i < n; i++) {
        dp[i][0] = true;
      }
   
      // with only one number, we can form a subset only when the required sum is equal to its value
      for (int s = 1; s <= sum; s++) {
        dp[0][s] = (num[0] == s ? true : false);
      }
   
      // process all subsets for all sums
      for (int i = 1; i < num.size(); i++) {
        for (int s = 1; s <= sum; s++) {
          // if we can get the sum 's' without the number at index 'i'
          if (dp[i - 1][s]) {
            dp[i][s] = dp[i - 1][s];
          } else if (s >= num[i]) {
            // else include the number and see if we can find a subset to get the remaining sum
            dp[i][s] = dp[i - 1][s - num[i]];
          }
        }
      }
   
      // the bottom-right corner will have our answer.
      return dp[num.size() - 1][sum];
    }
   };
   
   int main(int argc, char *argv[]) {
    SubsetSum ss;
    vector<int> num = {1, 2, 3, 7};
    cout << ss.canPartition(num, 6) << endl;
    num = vector<int>{1, 2, 7, 1, 5};
    cout << ss.canPartition(num, 10) << endl;
    num = vector<int>{1, 3, 4, 8};
    cout << ss.canPartition(num, 6) << endl;
   }

   還可以優化成只用一個 row 就解決：

   class SubsetSum {
   public:
    bool canPartition(const vector<int> &num, int sum) {
      vector<bool> dp(sum+1, false);
      dp[0] = true;
      if(num[0] <= sum) dp[num[0]] = true;
   
      for(int i=1; i<num.size(); i++) {
        for(int s=sum; s>=0; s--) {
          if(dp[s]) dp[s] = true;
          else if(num[i] <= s) dp[s] = dp[s-num[i]]; 
        }
      }
   
      return dp[sum];
    }
   };

2. Minimum Subset Sum Difference

3. [Count of Subset Sum]

   

   

   DP 解的實作如下：

   using namespace std;
   
   #include <iostream>
   #include <vector>
   
   class SubsetSum {
   public:
    int countSubsets(const vector<int> &num, int sum) {
      int n = num.size();
      vector<vector<int>> dp(n, vector<int>(sum + 1, 0));
   
      // populate the sum=0 columns, as we will always have an empty set for zero sum
      for (int i = 0; i < n; i++) {
        dp[i][0] = 1;
      }
   
      // with only one number, we can form a subset only when the required sum is
      // equal to its value
      for (int s = 1; s <= sum; s++) {
        dp[0][s] = (num[0] == s ? 1 : 0);
      }
   
      // process all subsets for all sums
      for (int i = 1; i < num.size(); i++) {
        for (int s = 1; s <= sum; s++) {
          // exclude the number
          dp[i][s] = dp[i - 1][s];
          // include the number, if it does not exceed the sum
          if (s >= num[i]) {
            dp[i][s] += dp[i - 1][s - num[i]];
          }
        }
      }
   
      // the bottom-right corner will have our answer.
      return dp[num.size() - 1][sum];
    }
   };
   
   int main(int argc, char *argv[]) {
    SubsetSum ss;
    vector<int> num = {1, 1, 2, 3};
    cout << ss.countSubsets(num, 4) << endl;
    num = vector<int>{1, 2, 7, 1, 5};
    cout << ss.countSubsets(num, 9) << endl;
   }