# Java solution with comments using dfs

• /*
Standard dfs.
We sum all the numbers in the array, if it's an odd number, retrun false;
otherwise the question is reduced to
find a subset of numbers, whos sum is total sum / 2.
We can use standard dfs to find if there is one
*/

public class Solution {
public boolean canPartition(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int sum = 0;
for(int i : nums){
if(map.containsKey(i)){
map.put(i, map.get(i) + 1);
}else{
map.put(i, 1);
}
sum += i;
}
if(sum % 2 == 1) return false;
return helper(map, sum / 2);
}

private boolean helper(Map<Integer, Integer> map, int target){
/*target is achieveable*/
if(map.containsKey(target) && map.get(target) > 0) return true;
/*dfs*/
for(int key : map.keySet()){
if(key < target && map.get(key) > 0){
map.put(key, map.get(key) - 1);
if(helper(map, target - key)) return true;
map.put(key, map.get(key) + 1);
}
}
return false;
}
}````

• I am wondering what's the time complexity of this kind of dfs solution. Exponential ?

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