Java solution DP(subsum problem) and backtracking(subsets II problem) with explanation


  • 2
    L

    method 1: backtracking + pruning
    same thought with subsetII

    public class Solution {
        public boolean canPartition(int[] nums) {
            if(nums == null || nums.length == 0) return false;
            int total = 0;
            for(int i = 0; i < nums.length; i++) total += nums[i];
            if(total % 2 != 0) return false; 
            List<Integer> list = new ArrayList<Integer>();
            Arrays.sort(nums);
            return helper(nums, list, 0, 0, total);
        }
    
        public boolean helper(int[] nums, List<Integer> list, int pos, int sum, int total)
        {
            if(total == 2 * sum) return true;
            if(total < 2 * sum) return false;
            boolean res = false;
            for(int i = pos; i < nums.length; i++)
            {
                if(i == pos || nums[i - 1] != nums[i])
                {
                    list.add(nums[i]);
                    res = res || helper(nums, list, i + 1, sum + nums[i], total);
                    if(res) return true;
                    list.remove(list.size() - 1);
                }
            }
            return false;
        }
    }
    

    method 2:
    DP: find if there is a subset that sum of the set is total/2.
    e.g. [1 2 4 1] ==> half = 8 % 2 = 4

    take matrix[1, 3] as example :

    matrix[1, 3] = matrix[0, 3] (don’t include 2) || matrix[0, (3 - 2) ] (include 2)

    0 1 2 3 4 (sum)
    ————————————————————
    1 T T F F F
    2 T T T T F
    4 T T T T T
    1 T T T T T

    public class Solution {
        public boolean canPartition(int[] nums) {
            if(nums == null || nums.length == 0) return false;
            int total = 0;
            for(int num : nums) total += num;
            if(total % 2 != 0) return false;
    
            return findSubsetSum(nums, total/2);// this questions --> find if there is a subset that can be added up to total/2.
        }
    
        public boolean findSubsetSum(int[] nums, int target)
        {
            boolean[] prevRow = new boolean[target + 1];
            //init
            prevRow[0] = true;
            for(int i = 1; i < prevRow.length; i++)
            {
                if(nums[0] == i) prevRow[i] = true;
            }
    
            for(int i = 1; i < nums.length; i++)
            {
                boolean[] cntRow = new boolean[target + 1];
                cntRow[0] = true;
                for(int j = 1; j < target + 1; j++)
                {
                    cntRow[j] = prevRow[j]; //don't include nums[i] into the subset
                    if(!cntRow[j] && j >= nums[i])
                    {
                        cntRow[j] = prevRow[j - nums[i]]; //include nums[i] into the subset
                    }
                }
                prevRow = cntRow;
            }
            return prevRow[target];
        }
    }
    

Log in to reply
 

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