Java найти все комбинации в массиве, которые добавляют до определенного числа

Question

я в настоящее время работаю над следующим вопросом из интервьюирования книги:

вам дает случайный массив из 50 уникальных целых чисел в диапазоне от 1 до 100 включительно. Напишите метод с использованием Java, который принимает положительное целое число как параметр и возвращает массив всех комбинаций чисел, которые добавляют к этому значению.

Например, если задан массив целых чисел [3,6,1,9,2,5,12] и передано целочисленное значение 9, вы должны вернуть [[3,6], [6, 1,2], [9], [3,1,5]]. Порядок возврата результатов в массив не имеет значения, хотя вы должны возвращать уникальные наборы (т. Е. [6,3] и [3,6] являются одинаковыми, и только один должен быть возвращен). Кроме того, отдельные результаты должны быть в том порядке, в котором они найдены (т.е. [6,1,2] должны быть возвращены, а не [1,2,6]).

Я достиг достойного прогресса, но я боюсь, что смогу решить это неправильно.

import java.util.*; 


public class findCombinations { 
    public static void main(String[] args) { 
    int number; 
    int[] list = new int[10]; 
    Scanner reader = new Scanner(System.in); 

    //fill the array 
    for (int i = 0; i < list.length; i++) { 
     number = (int)(Math.random() * 10) + 1; 
     list[i] = number; 
     for (int j = 0; j < i; j++) { //remove duplicates 
     if (list[i] == list[j]) { 
      i--; 
      break; 
     } 
     } 
    } 

    Arrays.sort(list); 

    //test output 
    for (int i = 0; i < list.length; i++) { 
     System.out.println(list[i]); 
    } 
    System.out.println("Enter a number: "); 
    int input = reader.nextInt(); 
    ArrayList<Integer> trimmedList = new ArrayList<Integer>(); 

    //cut out the numbers that are impossible to use 
    for (int i = 0; i < list.length; i++) { 
     if (list[i] <= input) { 
     trimmedList.add(list[i]); 
     } 
    } 
    //test output 
    printList(trimmedList); 

    ArrayList<Integer> comboList = new ArrayList<Integer>(); 
    System.out.println("Finding combinations..."); 

    for (int i = 0; i < trimmedList.size(); i++) { 
     int current = trimmedList.get(i); 
     if (current == input) { System.out.println(current); } 
     else if (current < input) { 
     comboList.add(current); 
     if (isCombo(comboList, input)) { 
      printList(comboList); 
     } 
     else { continue; } 
     } 
     else { continue; } 
    } 
    } 

    public static boolean isCombo(ArrayList<Integer> list, int input) { 
    ArrayList<Integer> combo = new ArrayList<Integer>(); 
    int sum = 0; 

    for (int i : list) 
     sum += i; 

    if (sum == input) { return true; } 
    else { return false; } 
    } 

    public static void printList(ArrayList<Integer> list) { 
    for (int i = 0; i < list.size(); i++) { 
     System.out.print(list.get(i)); 
    } 
    } 
} 

Я знаю, что это неполное, но я хотел бы спросить, если кто-либо имели какие-либо предложения или улучшение я мог бы сделать по этому поводу? Я отсортировал список и укоротил все целые числа, которые не будут использоваться, но теперь сложная часть находит все комбо.

Answer 1

Существует множество различных подходов к решению этой проблемы, каждый из которых имеет свои собственные достоинства, поэтому я бы не стал слишком беспокоиться о том, является ли ваш ответ «правильным» или нет ... пока он фактически решает проблема! Кроме того, интервьюер, скорее всего, будет больше заинтересован в вашем процессе мышления и стратегиях, которые вы используете, а не на 100% идеальном решении, написанном в течение нескольких минут на доске.

Вот несколько вещей, чтобы рассмотреть следующие вопросы:

• Как вы заметили, вы можете немедленно устранить любые целые числа больше, чем целевая величина.

• Вы по существу генерируете подмножества произвольного размера вашего стартового массива, поэтому Set, скорее всего, является самым полезным типом данных для работы. {2, 3} и {3, 2} следует рассматривать как идентичные, когда вы генерируете свой набор ответов.

• Целочисленное разбиение является проблемой NP-Complete. Это тяжело. Я думаю, вы взяли правильный подход, начиная с массива, а не с целевым значением.

• Существует множество алгоритмов для генерации комбинаций целых чисел из большего набора. Посмотрите на это SO answer для некоторых из них. Вы можете сгенерировать k размерные комбинации из вашего (уже отфильтрованного) стартового набора, для k от 1 до 50.

• На самом деле ... есть более прямые способы получить power set вашего стартового набора. Рассмотрим внутреннюю структуру набора мощности (см. Ниже). Перечислив несколько примеров, вы заметите естественное повторение своей стратегии идентификации подмножеств.

Поскольку вы генерируете эти комбинации, отбросьте любые элементы, которые не суммируются с вашим целевым значением.

Изображения Источник: https://en.wikipedia.org/wiki/Power_set

Answer 2

Поскольку это учебное упражнение, вы выиграете больше всего, если сможете решить это самостоятельно. Так что ...

советов:

1. Сортировка числа первого на правильном пути
2. Я хотел бы использовать рекурсию для итерации решения. Для частичной суммы только числа, меньшие определенного числа, являются возможными кандидатами для добавления в сумму ...
3. Выполните алгоритм в голове> до <, вы начинаете его кодировать.

---

И я согласен с тем, что @nbrooks говорит на тему того, что интервьюеры ищут. Вы должны уметь мыслить ... и объяснять свое мышление интервьюеру ... на уровне алгоритма. Именно это отличает отличных кандидатов от обычных.

Answer 3

Я понимаю, генерирую массив случайных чисел не является частью постановки задачи, но я думаю, что ваши трудности начинаются здесь.

Прежде всего, используйте коллекцию типа Set<Integer> для сбора генерируемых номеров; если набор достигнет желаемого размера. Если сгенерированный порядок важен, используйте LinkedHashSet.

Set<Integer> origSet = new HashSet<Integer>(); // fill with random numbers 

В какой-то момент у вас есть список номеров, для которых имеет значение заказ. Ведите этот список как List<Integer>. Список сохраняет порядок вашего исходного списка, чтобы вы могли производить комбинацию чисел в правильном порядке (т. Е. 6 предшествует 1, 1 предшествует 2).

List<Integer> origList = new ArrayList<Integer>(origSet); // use indexOf method to find index of a number 

Вы создаете второй отсортированный список; этот список - тот, который используется вашим алгоритмом рекурсии.

List<Integer> sortedList = new ArrayList<Integer>(origList); // sort this 

Вам не нужно обрезать список, потому что рекурсивный алгоритм обрезает любую ветвь без допустимого решения.

Рекурсивный алгоритм может генерировать комбо в меньшем количестве строк кода. Переупорядочение занимает еще несколько строк.