Java AC DFS solution with explanation

  • 0
    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){
            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
                return true;
            if(left<0) return false;
            //do dfs
            for(int i=0;i<nums.length;i++){
                    boolean r = helper(nums,left-nums[i],map,visited);
                    if(r) return true;
            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.