[C++] vector sum, dp table with vector

 

LeetCode: 416. Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/description/

Partition Equal Subset Sum - LeetCode

class Solution{
	public:
		
		vector<int> nums;
		vector<vector<optional<bool>>> dp;
		
		bool canPartition(vector<int>& nums) {
			int total = accumulate(nums.begin(), nums.end(), 0);
			if (total % 2 == 1) return false;
			int n = nums.size();
			int goal = total/2;
			this->nums = nums;
			this->dp = vector<vector<optional<bool>>>(n+1, vector<optional<bool>>(goal+1, nullopt));
			return dfs(0, goal);
		}
		
		bool dfs(int idx, int goal) {
			if (goal < 0) {
				return false;
			}
			
			if (idx == nums.size()) {
				return goal == 0;
			}
			
            if (dp[idx][goal] != nullopt) return dp[idx][goal] == true;

			if (dfs(idx+1, goal-nums[idx]) == true) {
				dp[idx][goal] = true;
				return true;
			}
			
			if (dfs(idx+1, goal) == true) {
				dp[idx][goal] = true;
				return true;
			}
			
			dp[idx][goal] = false;
			return false;
			
		}
		
};