Partition Problem (Equal Sum Subset)?

bool CanPartition(int[] nums)

int sum = nums.Sum();

Follow on:

if (sum % 2 != 0) return false;

int target = sum / 2;

bool[] dp = new bool[target + 1];

dp[0] = true;

foreach (int num in nums)

for (int j = target; j >= num; j--)

dp[j] = dp[j] || dp[j - num];

return dp[target];

Explanation:

Subset sum to check if half the total sum is achievable.

Sorting and Searching