Для заданного целочисленного массива (длиной n) найдите и верните все подмножества входного массива, используя рекурсию в Java

Question

Предположим, мой входной массив [15,20,12] Требуемый ответ - двумерный массив
Требуется следующий вывод:
[12
20
20 12
15
15 12
15 20
15 20 12
]

Answer 1

Отказ от ответственности:

1. Это моя оригинальная работа. Ни одна часть решения нигде не была скопирована.
2. Мое решение отлично работает для 3 элементов. Тем не менее, это должно быть улучшено для работы с массивами других размеров. Несмотря на это, я публикую его, чтобы OP или кто-либо другой могли расширить это решение для работы с массивом любого размера.
3. Этот вопрос близок к блоку питания, за исключением того факта, что блок питания не может иметь дублирующихся элементов. Если это исключение будет исключено из этого вопроса, будет доступно множество решений, например: 1 , 2 , 3 et c.

---

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = { 15, 20, 12 };
        System.out.println(Arrays.deepToString(subsets(arr)));
    }

    public static int[][] subsets(int input[]) {
        int[][] subarrs = new int[(int) Math.pow(2, input.length) - 1][input.length];
        int[] indices = { 0 };
        subsetsHelper(input, subarrs, 0, 0, 0, indices);
        return subarrs;
    }

    private static void subsetsHelper(int input[], int[][] subarrs, int index, int i, int j, int[] indices) {
        if (i == input.length) {
            subarrs[index] = input;
            return;
        }
        int[] subarr = new int[indices.length];
        for (int x = 0; x < subarr.length; x++) {
            subarr[x] = input[indices[x]];
        }
        subarrs[index] = subarr;
        if (j == input.length - 1) {
            subsetsHelper(input, subarrs, index + 1, i + 1, i + 1, new int[] { i + 1 });
        } else {
            subsetsHelper(input, subarrs, index + 1, i, j + 1, new int[] { i, j + 1 });
        }
    }
}

Выход:

 [[15], [15, 20], [15, 12], [20], [20, 12], [12], [15, 20, 12]]

Answer 2

Здесь вы go.

public static void main(String[] args) {

    int[] nums= {15, 20, 12};
    int[][] subsets = subsets(nums);
    for (int i = 1; i < subsets.length; i++) {
        System.out.println(Arrays.toString(subsets[i]));
    }
}

public static int[][] subsets(int input[]) {
    List<List<Integer>> list = new ArrayList<>();
    subsetsHelper(list, new ArrayList<>(), input, 0);
    return convertListToArray(list);
}

private static void subsetsHelper(List<List<Integer>> list , List<Integer> resultList, int [] nums, int start){
    list.add(new ArrayList<>(resultList));
    for(int i = start; i < nums.length; i++){
       // add element
        resultList.add(nums[i]);
       // Explore
        subsetsHelper(list, resultList, nums, i + 1);
       // remove
        resultList.remove(resultList.size() - 1);
    }
}

private static int[][] convertListToArray(List<List<Integer>> list) {
    int[][] array = new int[list.size()][];
    for (int i = 0; i < array.length; i++) {
        array[i] = new int[list.get(i).size()];
    }
    for(int i=0; i<list.size(); i++){
        for (int j = 0; j < list.get(i).size(); j++) {
            array[i][j] = list.get(i).get(j);
        }
    }
    return array;

}

1. Поскольку каждый рекурсивный вызов будет представлять здесь подмножество, добавьте resultList (см. Код рекурсии выше) к списку подмножеств в каждом вызове. 2. Проанализируйте элементы набора. 3. В каждой итерации добавляйте элементы в список explore (рекурсия) и делайте start = i + 1 до go через оставшиеся элементы массива. Удалить элемент из списка

Вывод:

[15]
[15, 20]
[15, 20, 12]
[15, 12]
[20]
[20, 12]
[12]

Answer 3

Непонятно, домашняя работа или практический случай. Вот как бы я решить это с помощью Guava PowerSet:

public static void main(String[] args) {
    Integer input[] = {15,20,12};
    List<Integer> rev = Lists.reverse(Arrays.asList(input));
    Set<Integer> indices = IntStream.range(0, input.length).boxed().collect(ImmutableSet.toImmutableSet());
    Object output[] = Sets.powerSet(indices).stream()
            .filter(indexset -> !indexset.isEmpty())
            .map(indexset -> indexset.stream().map(i -> rev.get(i)).collect(Collectors.collectingAndThen(toList(), Lists::reverse)))
            .map(List::toArray)
            .toArray();
    System.out.println(Arrays.deepToString(output));
}