## Subset Sum 系列

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;
}
``````