Java AC DFS solution with explanation


  • 0
    S
    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;
        }
    }

Log in to reply
 

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