JAVA Partition to K Equal Sum Subsets


  • 0
    N
    class Solution {
        public boolean canPartitionKSubsets(int[] nums, int k) {
            
            int sum = IntStream.of(nums).sum();
            if (sum % k !=0) {
                return false;
            }
            
            boolean[] used = new boolean[nums.length];
            int goal = sum/k;
            
            return findSets(nums, used, k, goal, 0, 0);
            
        }
        
        private boolean findSets(int[] nums, boolean[] used, int k, int goal, int sum, int s) {
            
            if (k == 0 && sum == goal) {
                return true;
            }
            
            if (sum == 0) {
                return findSets(nums, used, k-1, goal, goal, 0);
            } 
            
            if(sum < 0) {
                return false;
            }
            
            for (int i=s; i< nums.length; i++) {
                if (used[i]) {
                    continue;
                }
                used[i] = true;
                boolean found = findSets(nums, used, k, goal, sum - nums[i], i+1);
                if (found) {
                    return true;
                }
                used[i] = false;
            }
            return false;
        }
    }
    

Log in to reply
 

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