# C++ 5-line DFS solution with detailed explanation

• 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

1. if including current value `nums[i]` in the subset, check sub array up to position `i-1` against target `t-nums[i]`;
2. 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;
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.