Subset Sum 系列

還有一些題型也屬於這類,但不在 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;
    }
    

results matching ""

    No results matching ""