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), {})
Python Backtracking with Memoization Solution


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



Index
i
means we have availablenum
innums[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.
