Java DFS Solution with Pruning Beats 97%


  • 1
    Y

    This question can be converted to determine if we can find a subset such that the sum of elements is target (target = totalSum / 2), which is similar to LC 40 Combination Sum II.

    public class Solution {
        public boolean canPartition(int[] nums) {
            
            // compute target
            int sum = 0;
            int target = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % 2 != 0) {
                return false;
            }
            target = sum / 2;
            
            // find if there is a subset such that the sum of elements is target
            Arrays.sort(nums);
            return dfs(nums, target, 0);
        }
        
        private boolean dfs(int[] nums, int target, int st) {
            
            if (target == 0) {
                return true;
            }
            
            for (int i = st; i < nums.length && nums[i] <= target; i++) {
                
                // pruning
                if (i > st && nums[i] == nums[i-1]) {
                    continue;
                }
                
                if (dfs(nums, target - nums[i], i + 1)) {
                    return true;
                }
            }
            
            return false;
        }
    }
    

Log in to reply
 

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