# Python Backtracking with Memoization Solution

• ``````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), {})
``````

• 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;
}
}
``````

• This post is deleted!

• Hey man...

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

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

• This post is deleted!

• 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?

• @lekzeey I also have the same question here

• 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.

• @realisking oh that makes sense lol

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