416题求助

Question

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

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

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

加油！：）