Python interview with a FAANG engineer: Split array sum equally

[blasttrash]

lol he definitely knew that question before. Or else how the hell would someone **straight away jump into dp table** lol. dp table is an optimization once you have formulated your recursive formula or actually programmed recursive solution and there's repeated work.

He jumped straight into this optimization without talking about why one would need it in the first place. and it was funny that he was not using words like dynamic programming for first few minutes trying to sound like he never saw the question.

[smalex]

A little bit complicated.

Much easier here

class Solution {
public:
bool canPartition(vector<int>& nums) {
sort(nums.begin(), nums.end());
int total = accumulate(nums.begin(), nums.end(), 0);
if (total % 2 != 0) {
return false;
}
total /= 2;
vector<bool> dp(total + 1, false);
dp[0] = true;
for (auto num : nums) {
for (int i = total; i > 0; i--) {
if (i >= num && dp[i - num]) {
dp[i] = true;
}
}
}
return dp[total];
}
};

[z]

This solution is not optimal - numbers can be in a huge range, and dp table will not fit in memory. This particular problem is a typical 0/1 knapsack - which is NP-complete, and apparently has no significant optimizations, therefore this problem can be solved only as brute force.