Упражнения на Java: разделите данный массив целых чисел на заданные k непустых подмножеств, все суммы которых равны

Java Basic: упражнение 201 с решением

Напишите программу на Java, чтобы разделить данный массив целых чисел на заданные k непустых подмножеств, все суммы которых равны. Вернуть true, если все суммы равны, иначе вернуть false.

Пример:
nums = {1,3,3,5,6,6}, k = 4;
4 подмножества (5,1), (3, 3), (6), (6) с равными суммами.

Иллюстрированная презентация:

Пример решения:

Java-код:

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);
 }
}

Пример вывода:

 Исходный массив: [1, 3, 3, 5, 6, 6]
Цель подмножеств: 4
После удаления повторяющихся символов: правда

Блок - схема:

Редактор кода Java:

Компания: LinkedIn

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите Java-программу для удаления повторяющихся букв и упорядочения в лексикографическом порядке из заданной строки, которая содержит только строчные буквы.
Далее: Напишите программу на Java, чтобы найти общее количество непрерывных подмассивов в данном массиве целых чисел, сумма которых равна данному целому числу.