Упражнения на Java: найдите все уникальные комбинации из набора номеров кандидатов
Java Basic: упражнение 209 с решением
Напишите программу на Java, чтобы найти все уникальные комбинации из набора номеров кандидатов. Сумма чисел будет равна заданному целевому числу.
Пример решения:
Java-код:
import java.util.*;
class Main {
private static < K, V > void insert(Map < K, List < V >> hashMap, K key, V value) {
if (!hashMap.containsKey(key)) {
hashMap.put(key, new ArrayList < > ());
}
hashMap.get(key).add(value);
}
public static void Subsets(int[] A, int i, int j) {
System.out.print("{ ");
for (int k = i; k <= j; k++) {
System.out.print(A[k] + " ");
}
System.out.println("}");
}
public static void Subsets(int[] A, int sum) {
Map < Integer, List < Integer >> hashMap = new HashMap < > ();
insert(hashMap, 0, -1);
int sum_so_far = 0;
for (int index = 0; index < A.length; index++) {
sum_so_far += A[index];
if (hashMap.containsKey(sum_so_far - sum)) {
List < Integer > list = hashMap.get(sum_so_far - sum);
for (Integer value: list) {
Subsets(A, value + 1, index);
}
}
insert(hashMap, sum_so_far, index);
}
}
public static void main(String[] args) {
{
Scanner s = new Scanner(System.in);
System.out.println("Input number of elements of the array: ");
int n = s.nextInt();
System.out.println("Input number format: 2 3 4 5: ");
int arr[] = new int[n];
System.out.println("Enter elements:");
for (int i = 0; i < n; i++)
arr[i] = s.nextInt();
System.out.println("Enter target sum:");
int sum = s.nextInt();
int A[] = new int[arr.length];
A = Arrays.copyOf(arr, arr.length);
System.out.println("A solution set is:");
Subsets(A, sum);
System.exit(0);
}
}
}
Пример вывода:
Введите количество элементов массива: 3 Формат ввода номера: 2 3 4 5: Введите элементы: 6 7 8 Введите целевую сумму: 21 Набор решений: {6 7 8}
Блок - схема:
Редактор кода Java:
Внесите свой код и комментарии через Disqus.
Предыдущий: Напишите программу на Java, чтобы проверить, является ли данное целое число степенью 2 или не использует время O (1).
Далее: Напишите программу на Java, которая будет соответствовать любому отдельному символу (использовать?) Или любой последовательности символов *), включая пустой.
Каков уровень сложности этого упражнения?
Новый контент: Composer: менеджер зависимостей для PHP , R программирования
disqus2code