Partition Equal Subset Sum
1.先除以2
2.每個DP位置每次都往前j-nums[i]看該位置有沒有更新
換句話說就是從dp[0]開始出發,
第一次先更新 0 nums[0]
第二次更新0 + nums[1], nums[0] + nums[1]
樹狀圖展開(Backtracking or DFS)
最後檢查dp[sum/2]這個位置有沒有訪問過
Loop 寫法
bool canPartition(vector<int>& nums) { int sum = 0; for(int i = 0; i < nums.size(); i++) sum += nums[i]; if(sum%2) return false; vector<int> dp(sum/2+1,0); dp[0] = 1; for (int i = 0; i < nums.size(); i++) { for (int j = sum/2; j >= nums[i]; j--) dp[j] = dp[j] || dp[j-nums[i]]; } return dp[sum/2]; }
Recursion: 會TLE XD
vector<int> dp; vector<int> nums; bool canPartition(vector<int>& nums) { int sum = 0; for(int i = 0; i < nums.size(); i++) sum += nums[i]; if(sum%2) return false; dp.resize(sum/2+1,0); this->nums = nums; dfs(0, 0); return dp[sum/2]; } void dfs(int cur, int index) { if(index + 1 < nums.size()) { dfs(cur, index + 1); dfs(cur + nums[index], index + 1); } if(cur < dp.size()) { if(dp[cur] == 1) return; else dp[cur] = 1; } }