第416题，不小心写出了一个14ms的超快解法，但自己都不知道到底对不对，求挑错！！！

class Solution {
    public boolean canPartition(int[] nums) {
        Arrays.sort(nums);
        List<Integer> list1=new ArrayList<>();
        List<Integer> list2=new ArrayList<>();
        int sum1=0;
        int sum2=0;
        for(int i=0;i<nums.length;i++){
            if(i%2==0){
                list1.add(nums[i]);
                sum1+=nums[i];
            }else{
                list2.add(nums[i]);
                sum2+=nums[i];
            }
        }
        if((sum1+sum2)%2==1) return false;
        int sum=0;
        for(int i:nums){
            sum+=i;
            if(sum*2==sum1+sum2) return true;
        }
        while(sum1!=sum2){
            if(list1.isEmpty() || list2.isEmpty()) break;
            if(sum1>sum2){
                int diff=(sum1-sum2)/2;
                int index=0;
                for(int i=list1.size()-1;i>0;i--){
                    if(Math.abs(diff-list1.get(i))<=Math.abs(diff-list1.get(i-1))){
                        index=i;
                        break;
                    }
                }
                int item=list1.remove(index);
                sum1-=item;
                sum2+=item;
            }else{
                int diff=(sum2-sum1)/2;
                int index=0;
                for(int i=list2.size()-1;i>0;i--){
                    if(Math.abs(diff-list2.get(i))<=Math.abs(diff-list2.get(i-1))){
                        index=i;
                        break;
                    }
                }
                int item=list2.remove(index);
                sum1+=item;
                sum2-=item;
            }
        }
        return sum1==sum2;
    }
}





代码如上，希望大神帮帮忙，这个解法到底对不对？

这类Greedy解法在数字大小和数组长度差别不大时能得出比较好的近似结果，但是如果数字很大而数组比较短就很可能不行了，比如：{15, 48, 49, 69, 70, 71, 150}有解（48+49+69+70 == 15+71+150 == 236），但是这段代码返回的是false。

这种方法如果能保证给出正确解的话，你就等于已经证明了P=NP啦

。。。我一直以为这道题是背包问题？

2011051305 发表于 2017-8-23 05:50
。。。我一直以为这道题是背包问题？

我也看了backpack解法。
但这个到底对不对呢。。。

大概看懂了你的解法，基本就是先从一个还不错的 近似解开始，greedy的方式开始move element；

因为都是positive element, 于是都从 当前sum比较高的move 到比较低的； 同时因为，we can move each element at most once to achieve the optimal solution, if exists. Therefore we just need to remove it.

Cute idea, but I am not sure the greedy strategy for "removing" is correct, but it should be a very good strategy, that I cannot manually find any counter-examples..

Do you have a idea of proof in mind?

outlier_2017 发表于 2017-8-23 05:56
我也看了backpack解法。
但这个到底对不对呢。。。

我觉得是对的，你这个做法应该就是贪心的思路。每次去其中最大的k个elements（本题k=2）然后把这些elements塞到whichever smaller subsets里去。
用数学归纳法可以证明正确性

但是这个方法不是O(nlogn)的么？ 动态规划应该是O(sum*n)的 （sum是input数字之和）所以说明利扣的test cases 应该都是 logn比sum小的？。。。（我好鸡贼。。）

内什么。。不是大神。。。大神是@fentoyal  他每次都救我于水火。。 我是已经毕业了没找到工作的弱鸡 == 顺便打滚求安慰。。

试一下这组测试数据：
[1, 5, 7, 23, 24]

stellari 发表于 2017-8-23 08:27
这类Greedy解法在数字大小和数组长度差别不大时能得出比较好的近似结果，但是如果数字很大而数组比较短就很 ...

是的，我刚才也构造了一组。

Leetcode的测试数据还是太弱了。

2011051305 发表于 2017-8-23 06:54
我觉得是对的，你这个做法应该就是贪心的思路。每次去其中最大的k个elements（本题k=2）然后把这些elemen ...

没事没事，亚麻保底好吧

一看望去好复杂，感觉不适合面试这种高强度快节奏~