416题求助

Question

class Solution {
    public boolean canPartition(int[] nums) {

        if(nums == null || nums.length == 0)
            return true;
        
        int sum = 0;
        for (int i = 0; i < nums.length; i ++){
            sum += nums[i];
        }
        
        //sum为奇数时直接return false
        if (sum % 2 == 1)
            return false;
        
        //sum is even
        int target = sum/2;
        //只要找到target就好了，剩下的元素和一定也为sum/2;
        return helper(nums, target, 0);
    }
    
    private boolean helper(int[] nums, int target, int index){
        if (target == 0)
            return true;
        if (target < 0)
            return false;
        if (index  == nums.length)
            return false;
        //选或者不选
        return helper(nums,target,index + 1) || helper(nums,target - nums[index],index + 1);
    }
}

我这个算法是2^n的时间复杂度，我想用一个二维数据memo记录一下重复被调用的函数，但是没想出来，可以麻烦老师给个idea吗？还是说最好还是用dp写

Link:    https://leetcode.com/problems/partition-equal-subset-sum/

Answer 1

liuyubobobo 2019-05-29 02:19:47

记忆化搜索的思路可以参考这里：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0416-Partition-Equal-Subset-Sum/cpp-0416/main.cpp

其实完全是背包问题，请仔细比较这个问题和背包问题之间的区别和联系，看看能不能更深入的理解背包问题？

加油！：）