Buckles — divided into k equal subsets

I. Title:

Given an integer array nums and a positive integer k, find out if it is possible to divide the array into k non-empty subsets whose summation is all equal.

Example 1: Input: nums = [4, 3, 2,3, 5, 2, 1], k = 4 Output: True Description: It is possible to divide it into four subsets (5), (1,4), (2,3), (2,3) equal to the sum. 1 <= k <= len(nums) <= 16 0 < nums[I] < 10000Copy the code

Ii. Ideas:

Target =sum(nums)/k; target=sum(nums)/k; Once we get the target value, we can get some cases that must be false, such as

1. The target value is not an integer
2. Nums has a value greater than target

If nums has a value equal to target, put all elements of nums into groups of length K. Return true if nums has just been put into groups. For putting groups we call it searching for elements to put into groups, and for k subsets we just need a for loop. Using recursion we can always search. You can keep adding to the group array by simply changing the currently searched value. If you do not understand the idea, please combine the code analysis.

Iii. Code:

public classDivided intokIt's an equal subset{
    public static void main(String[] args) {divided into k equal subsets a =newDivided into k equal subsets ();int[] nums = {4.3.2.3.5.2.1};
        System.out.println(a.canPartitionKSubsets(nums,4));
    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k > 0) return false;
        // The target value is sum/k
        int target = sum / k;
        // Sort the nums array in ascending order
        Arrays.sort(nums);
        int row = nums.length - 1;
        // If the maximum value is greater than the target value, the array must not meet the condition, so return false
        if (nums[row] > target) return false;
        // If there is k--, row-- equal to the target value
        while (row >= 0 && nums[row] == target) {
            row--;
            k--;
        }
        return search(new int[k], row, nums, target);
    }


    // The nums function searches for each number added to groups, and is equal to target, and row represents the number currently added to groups
    public boolean search(int[] groups, int row, int[] nums, int target) {
        // if there are no numbers in nums, then all numbers are put into groups
        if (row < 0) return true;
        // Notice that row-- is assigned first, and then --
        int v = nums[row--];
        // Iterate over k subsets of groups
        for (int i = 0; i < groups.length; i++) {
            if (groups[i] + v <= target) {
                groups[i] += v;
                if (search(groups, row, nums, target)) return true;
                // can't add to groups, subtract it, and backtrack
                groups[i] -= v;
            }
            // Break the loop, or return false, if all numbers cannot be placed in groups, or if no values add, or if they are equal to target;
            if (groups[i] == 0) return false;
        }
        return false; }}Copy the code