12ms Java Backtracking Solution beating 91%


  • 0
    Z

    Since the largest number will either be in one or the other two resulting subsets, I first added the largest number to my solution path, and start backtracking.

    public class Solution {
        class DFSType {
            boolean res;
            int path;
        }
        
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length <= 1) return false;
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
            }
            if (sum % 2 != 0) return false;
            int target = sum / 2;
            Arrays.sort(nums);
            DFSType dfs = new DFSType();
            dfs.res = false;
            dfs.path = nums[nums.length - 1];
            helper(dfs, nums, nums.length - 2, target);
            return dfs.res;
        }
        
        private void helper(DFSType dfs, int[] nums, int pos, int target) {
            if (dfs.res || dfs.path > target) return;
            if (dfs.path == target) {
                dfs.res = true;
                return;
            }
            
            for (int i = pos; i >= 0; i--) {
                if (i == pos || nums[i] != nums[i + 1]) {
                    dfs.path += nums[i];
                    helper(dfs, nums, i - 1, target);
                    dfs.path -= nums[i];
                }
            }
        }
    }
    

Log in to reply
 

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