I'm not so sure about the complexity. It looks like it would be O(n^2 log(n)) but in practice it's very fast (at least with the OJ's test case) beating 97.51%, so I think it would be around O(nlogn) in practice.

The basic idea is to sort the array, calculate half of the total sum.

Create a variable called *currentSum*, then use binary search to look for the element that if add it to our *currentSum* we'll get closest to the *halfsum*. If that element is in the array already, it means the array can be partitioned.

One small note here is when I was designing this algo, I thought I could do it O(nlogn) (without the outer while loop), but the inner while loop alone would fall test case like:

2 3 4 6 15 20

So I added the outer while loop which makes the algo runs correctly but to me, that could lead to worst case is n^2 * log(n)

Anyways, no more bs, here is the code.

```
public boolean canPartition(int[] nums) {
int sum = 0;
for (int i : nums) sum += i;
if ((sum & 1) == 1) return false;
int half = sum / 2;
Arrays.sort(nums);
int start = nums.length;
while (start > 0) {
int right = start;
int goal = half;
while (true) {
int idx = Arrays.binarySearch(nums, 0, right, goal);
if (idx >= 0) {
return true;
} else {
if (idx < 0) idx = ~idx;
if (idx == 0) break;
idx--; // get the one right before
goal -= nums[idx];
right = idx; // from now, we'll only search in the right size of idx
}
}
start--;
}
return false;
}
```