Java Solution using combination sumII, beat 96.25%


  • 0
    L
    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 combinationSum(nums, 0, total / 2);
        }
        
        public boolean combinationSum(int[] candidates, int index, int target) {
            if (target < 0) return false;;
            if (target == 0) {
                return true;
            }
            for (int i = index; i < candidates.length; i++) {
                if (canGo(candidates, index, i)) {
                    if (combinationSum(candidates, i + 1, target - candidates[i])) {
                        return true;
                    }
                    
                }
            }
            return false;
        }
        
        public boolean canGo(int[] candidates, int index, int i) {
            while (candidates[index] != candidates[i]) index++;
            return index == i;
        }
    

  • 0
    X
    This post is deleted!

Log in to reply
 

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