w3resource

Java: Divide a given array of integers into given k non-empty subsets whose sums are all equal

Java Basic: Exercise-201 with Solution

Write a Java program to divide a given array of integers into given k non-empty subsets whose sums are all equal. Return true if all sums are equal otherwise return false.

Example:
nums = {1,3,3,5,6,6}, k = 4;
4 subsets (5,1), (3, 3), (6), (6) with equal sums.

Visual Presentation:

Java Basic Exercises: Divide a given array of integers into given k non-empty subsets whose sums are all equal

Sample Solution:

Java Code:

// Import Arrays and other utility classes from java.util package
import java.util.Arrays;

// Main class for the solution
public class Solution {
    // Main method to execute the solution
    public static void main(String[] args) {
        // Sample input array and target value for testing subset partitioning
        int[] nums = {1, 3, 3, 5, 6, 6};
        int target = 4;

        // Display the original array
        System.out.print("Original Array: " + Arrays.toString(nums));

        // Display the target value for subsets
        System.out.print("\nTarget of subsets: " + target);

        // Display the result after removing duplicate characters using partition_k_subsets function
        System.out.print("\nAfter removing duplicate characters: " + partition_k_subsets(nums, target));
    }

    // Function to recursively search for valid subsets with a specific sum
    static boolean search_subset(int used, int n, boolean[] flag, int[] nums, int target) {
        // Base case: all elements used, subset found
        if (n == 0) {
            return true;
        }

        // Check if the current subset has not been considered before
        if (!flag[used]) {
            // Mark the current subset as visited
            flag[used] = true;

            // Calculate the remaining sum needed for the subset
            int remain_num = (n - 1) % target + 1;

            // Iterate through the elements in the array
            for (int i = 0; i < nums.length; i++) {
                // Check if the current element is not used in the subset and its value is less than or equal to the remaining sum
                if ((((used >> i) & 1) == 0) && nums[i] <= remain_num) {
                    // Recursively search for the subset with the updated parameters
                    if (search_subset(used | (1 << i), n - nums[i], flag, nums, target)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    // Function to partition an array into k subsets with equal sum
    public static boolean partition_k_subsets(int[] nums, int k) {
        // Calculate the total sum of the elements in the array
        int sum = Arrays.stream(nums).sum();

        // Check if the sum is not divisible by k, return false
        if (sum % k > 0) {
            return false;
        }

        // Create a boolean array to track visited subsets
        boolean[] flag = new boolean[1 << nums.length];

        // Call the recursive search_subset function to check for valid subsets
        return search_subset(0, sum, flag, nums, sum / k);
    }
} 

Sample Output:

Original Array: [1, 3, 3, 5, 6, 6]
Target of subsets: 4
After removing duplicate characters: true

Flowchart:

Flowchart: Java exercises: Divide a given array of integers into given k non-empty subsets whose sums are all equal

Java Code Editor:

Company:  LinkedIn

Contribute your code and comments through Disqus.

Previous: Write a Java program to remove duplicate letters and arrange in lexicographical order from a given string which contains only lowercase letters.
Next: Write a Java program to find the total number of continuous subarrays in a given array of integers whose sum equals to an given integer.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://w3resource.com/java-exercises/basic/java-basic-exercise-201.php