# Java solution DP(subsum problem) and backtracking(subsets II problem) with explanation

• method 1: backtracking + pruning
same thought with subsetII

``````public class Solution {
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0) return false;
int total = 0;
for(int i = 0; i < nums.length; i++) total += nums[i];
if(total % 2 != 0) return false;
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
return helper(nums, list, 0, 0, total);
}

public boolean helper(int[] nums, List<Integer> list, int pos, int sum, int total)
{
if(total == 2 * sum) return true;
if(total < 2 * sum) return false;
boolean res = false;
for(int i = pos; i < nums.length; i++)
{
if(i == pos || nums[i - 1] != nums[i])
{
res = res || helper(nums, list, i + 1, sum + nums[i], total);
if(res) return true;
list.remove(list.size() - 1);
}
}
return false;
}
}
``````

method 2:
DP: find if there is a subset that sum of the set is total/2.
e.g. [1 2 4 1] ==> half = 8 % 2 = 4

take matrix[1, 3] as example :

matrix[1, 3] = matrix[0, 3] (don’t include 2) || matrix[0, (3 - 2) ] (include 2)

0 1 2 3 4 (sum)
————————————————————
1 T T F F F
2 T T T T F
4 T T T T T
1 T T T T T

``````public class Solution {
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0) return false;
int total = 0;
for(int num : nums) total += num;
if(total % 2 != 0) return false;

return findSubsetSum(nums, total/2);// this questions --> find if there is a subset that can be added up to total/2.
}

public boolean findSubsetSum(int[] nums, int target)
{
boolean[] prevRow = new boolean[target + 1];
//init
prevRow[0] = true;
for(int i = 1; i < prevRow.length; i++)
{
if(nums[0] == i) prevRow[i] = true;
}

for(int i = 1; i < nums.length; i++)
{
boolean[] cntRow = new boolean[target + 1];
cntRow[0] = true;
for(int j = 1; j < target + 1; j++)
{
cntRow[j] = prevRow[j]; //don't include nums[i] into the subset
if(!cntRow[j] && j >= nums[i])
{
cntRow[j] = prevRow[j - nums[i]]; //include nums[i] into the subset
}
}
prevRow = cntRow;
}
return prevRow[target];
}
}
``````

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