Java solution with comments using dfs


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

  • 0
    A

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


Log in to reply
 

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