**Key observation:** Such partition exists if and only if

- The array sum
`sum`

is even; - There is a subset with sum equal to target
`sum/2`

.

For sub array up to position `i`

against target `t`

, the DFS algorithm will be straightforward to check

- if including current value
`nums[i]`

in the subset, check sub array up to position`i-1`

against target`t-nums[i]`

; - otherwise, check sub array up to position
`i-1`

against target`t`

.

And we claim the desired partition exists if either 1 or 2 holds.

**Note:** Inspired by @YJL1228 , for DFS, **pre-process array nums with sorting is necessary** since the

`dfs`

routine needs to return by traversing as fewer numbers as possible. So traversing larger numbers first will speed up to decide whether a desired subsum exists, i.e., *if you want to fail, make sure to fail quickly*.

```
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
sort(nums.begin(), nums.end()); rend = nums.rend();
return !(sum%2) && dfs(nums.rbegin(), sum/2);
}
// if sub array up to position `i` has a subset with sum equal to target `t`
bool dfs(vector<int>::reverse_iterator i, int t) {
return (i == rend || t <= 0)? false : !t || t == *i || dfs(i+1, t-*i) || dfs(i+1, t);
}
vector<int>::reverse_iterator rend;
```