416. Partition Equal Subset Sum

class Solution {public:    bool canPartition(vector<int>& nums) {        int total_sum = 0;        for (int i = 0; i < nums.size(); i++) {            total_sum += nums[i];        }        if (total_sum % 2 == 1) return false;        int target_sum = total_sum / 2;        // needed a hint to figure out what I am solving for here. was        // thinking an initial complete search algo but should have        // realized easier solve would be to find a more specific data        // point to check. like find the halving point. that is simple        // metric for DP to do. dp array to keep track of what sums as        // possible and build from there.        std::vector<bool> save(target_sum + 1, false);        save[0] = true;        for (int i = 0; i < nums.size();             i++) {  // iter through all numbers and backwards through all                     // possible sums.            for (int k = save.size() - 1; k >= 0; k--) {                // had to look at hint for why i have to iterate k                // backwards, understood after that if since save is being                // modified in place, any changes made to previous index                // will be called back at future indexes. best solution is                // to go backwards so smaller numbers do not snowball from                // repeating in use.                if (save[k] && k + nums[i] < save.size())                    save[k + nums[i]] = true;                // std::cout << k + nums[i] << " " << k << " " << i << " "                // << nums[i] << endl;            }        }        // for (int i = 0; i < save.size(); i++) {        //     std::cout << save[i] << " ";        // }        return save[target_sum];    }};