# Java AC DFS solution with explanation

• ``````public class Solution {
public boolean canPartition(int[] nums) {
int N = nums.length;
/*
given the contraints below, the sum will not be overflowed
Each of the array element will not exceed 100.
The array size will not exceed 200.
*/
int sum=0;
for(int n:nums){
sum+=n;
}
if(sum%2==1) return false;
int half = sum/2;
//this map is to remember duplicate case result
Map<Integer,Boolean> map = new HashMap<Integer,Boolean>();
return helper(nums,half,map,new boolean[N]);
}

boolean helper(int[] nums, int left, Map<Integer,Boolean> map, boolean[] visited) {
if(map.get(left)!=null) return map.get(left);
//reach the point where subset sum is half of total sum
if(left==0){
return true;
}

if(left<0) return false;
//do dfs
for(int i=0;i<nums.length;i++){
if(!visited[i]){
visited[i]=true;
boolean r = helper(nums,left-nums[i],map,visited);
if(r) return true;
visited[i]=false;
}
}
map.put(left, false);
return false;
}
}``````

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