w3resource

Java Exercises: 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.

Pictorial 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 java.util.*;

public class Solution {
 public static void main(String[] args) {
  int[] nums = {1,3,3,5,6,6};
  int target = 4;
  System.out.print("Original Array: " + Arrays.toString(nums));
  System.out.print("\nTarget of subsets: " + target);
  System.out.print("\nAfter removing duplicate characters: " + partition_k_subsets(nums, target));
 }
 static boolean search_subset(int used, int n, boolean[] flag, int[] nums, int target) {
  if (n == 0) {
   return true;
  }

  if (!flag[used]) {
   flag[used] = true;
   int remain_num = (n - 1) % target + 1;
   for (int i = 0; i & lt; nums.length; i++) {
    if ((((used >> i) & 1) == 0) && nums[i] & lt; = remain_num) {
     if (search_subset(used | (1 & lt; & lt; i), n - nums[i], flag, nums, target)) {
      return true;
     }
    }
   }
  }
  return false;
 }

 public static boolean partition_k_subsets(int[] nums, int k) {
  int sum = Arrays.stream(nums).sum();
  if (sum % k > 0) {
   return false;
  }
  boolean[] flag = new boolean[1 & lt; & lt; nums.length];
  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.



Follow us on Facebook and Twitter for latest update.

Java: Tips of the Day

How to remove leading zeros from alphanumeric text?

Regex is the best tool for the job; what it should be depends on the problem specification. The following removes leading zeroes, but leaves one if necessary (i.e. it wouldn't just turn "0" to a blank string).

s.replaceFirst("^0+(?!$)", "")

The ^ anchor will make sure that the 0+ being matched is at the beginning of the input. The (?!$) negative lookahead ensures that not the entire string will be matched.

Test harness:

String[] in = {
    "01234",         // "[1234]"
    "0001234a",      // "[1234a]"
    "101234",        // "[101234]"
    "000002829839",  // "[2829839]"
    "0",             // "[0]"
    "0000000",       // "[0]"
    "0000009",       // "[9]"
    "000000z",       // "[z]"
    "000000.z",      // "[.z]"
};
for (String s : in) {
    System.out.println("[" + s.replaceFirst("^0+(?!$)", "") + "]");
}

Ref: https://bit.ly/2Qdcl8a