Python Backtracking with Memoization Solution


  • 2
    class Solution(object):
        def canFindSum(self, nums, target, ind, n, d):
            if target in d: return d[target] 
            if target == 0: d[target] = True
            else:
                d[target] = False
                if target > 0:
                    for i in xrange(ind, n):
                        if self.canFindSum(nums, target - nums[i], i+1, n, d):
                            d[target] = True
                            break
            return d[target]
        
        def canPartition(self, nums):
            s = sum(nums)
            if s % 2 != 0: return False
            return self.canFindSum(nums, s/2, 0, len(nums), {})
    

  • 0

    Here is Java Version:

    public class Solution {
    
    	public boolean canPartition(int[] nums) {
    		Arrays.sort(nums);
    		int sum = 0;
    		for (int num : nums)
    			sum += num;
    		if (sum % 2 == 1)
    			return false;
    		return backtracking(nums, 0, sum, 0);
    	}
    
    	private static boolean[] choices = { true, false };
    
    	private boolean backtracking(int[] nums, int sumSoFar, int sum, int k) {
    		for (boolean choice : choices) {
    			if (choice) {
    				sumSoFar += nums[k];
    			} else {
    				sumSoFar -= nums[k];
    			}
    
    			if (sumSoFar == sum / 2)
    				return true;
    			if (k + 1 == nums.length || sumSoFar > sum / 2)
    				return false;
    			if (backtracking(nums, sumSoFar, sum, k + 1))
    				return true;
    		}
    		return false;
    	}
    }
    

  • 0
    S
    This post is deleted!

  • 0
    W

    Hey man...

    I think our dear admin just added a test case yesterday... And your code got TLE for that one...

    @administrators


  • 0

    @whglamrock Thanks, I just added memoization to my code using a dict.


  • 0
    I
    This post is deleted!

  • 1
    L

    Thank you so much! But please why does memoizing only the target work? Shouldn't the memoization be also associated with the index as well?


  • 0
    C

    @lekzeey I also have the same question here


  • 0

    @chamberlian1990 @lekzeey

    Index i means we have available num in nums[i:n], if we can't find a possible answer in previous steps with more candidates, surely we can't find one with less candidates. Check my post here if my explanation still confuses you.


  • 0
    L

    @realisking oh that makes sense lol


Log in to reply
 

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