Список подмножеств, из которых их элементы складываются с использованием рекурсии

Question

Я пишу эту функцию, в которую я хочу напечатать все подсписки данного списка с целыми числами.Сумма этих целых чисел должна быть равна заданному числу n.Существует также справочная переменная i, которая начинается со значения 0. И список, и каждый подсписок являются ArrayList.Таким образом, метод выглядит следующим образом:

public static void printSublists(ArrayList numbers, ArrayList sublist, int n,
            int i) {

        if (sublist.sum() == n) {
            System.out.println(sublist.toString());
        } 
        else {
            for (int j = 0; j < numbers.size(); j++) {
                sublist.add(numbers.get(i));
                printSublists(numbers, sublist, n, i + 1);
                sublist.remove(numbers.get(i));
            }
        }
    }

Конечно, у меня уже есть метод sum().Метод делает это сейчас: скажем, numbers = [1, 3 , 4] и n == 4, тогда метод должен вывести [4] и [1 ,3], но он печатает только [1, 3]?Я думаю, что цикл for должен сделать трюк правильно?Я был бы признателен, если бы кто-то поставил меня на правильный путь.

обновление: значения, которые я даю методу:

numbers = [1, 3, 4]
n = 4
i = 0
sublist = []

ОБНОВЛЕНИЕ 2:

Я забылсказать, что я хочу, чтобы это было рекурсивно:)

Answer 1

@Test
public void test() {
    printSublists(new HashSet<Integer>(Arrays.asList(2, 3, 4, 1, 2)), new HashSet<Integer>(), 4);
}

private void printSublists(Set<Integer> numbers, Set<Integer> subList, int expected) {

    for (Integer element : numbers) {
        subList.add(element);
        if (sum(subList) == expected) {
            System.out.println("result =" + subList);
        }
        Set<Integer> listWithoutElement = withoutElement(numbers, element);
        printSublists(listWithoutElement, subList, expected);
        subList.remove(element);

    }
}

private Set<Integer> withoutElement(Set<Integer> numbers, Integer element) {
    Set<Integer> newList = new HashSet<Integer>(numbers);
    newList.remove(element);
    return newList;
}

private int sum(Collection<Integer> sublist) {
    int sum = 0;
    for (Integer e : sublist) {
        sum += e;
    }
    return sum;

}

Вот ваше решение.Эта проблема должна быть для наборов, а не для списка.

Если вы установили [2,3,4,1,2] , решение должно быть [3,1][4] [2,2] .Тогда проблема должна быть рекурсивной.Вы должны удалить дублирование, конечно:)

Answer 2

Рекурсия останавливается, когда вы видите первый подсписок с суммой n.Проблема не только в цикле, но и в критериях выхода. Ваша рекурсивная функция должна прекратиться, когда длина подсписка равна 0.

---

Здесь я только что написал работающее, рекурсивное решение вашей проблемы.Это отличается, но я не смог исправить твою.Пока вы начинаете с пустого подсписка, я решил начать рекурсию с полного списка, разделив его на более мелкие подсписки.Это создает древовидную структуру:

                        [1234]
                     [123]  [234]
                   [12] [23]   [34]
                  [1][2]  [3]    [4]

Мы сразу видим, что мы должны идти «вправо», пока не достигнем первого листа (1), затем мы идем только «налево».Таким образом, мы посещаем все подсписки только один раз.

Вот идея, написанная на Java:

public static void main (String[] args) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(1);
  list.add(3);
  list.add(4);
  list.add(0);
  printSublists(list, list, 4, true, 0);
}

public static void printSublists(List<Integer> numbers, List<Integer> sublist, int n, boolean walkRight, int level) {

  // the test
  if (sum(sublist) == n)
     System.out.println(sublist);

  // the exit criteia (leaf reached)
  if (sublist.size() == 1)
     return;

  // visit the right sublist
  if (walkRight) 
    printSublists(numbers, sublist.subList(0, sublist.size()-1), n, walkRight, level+1);

  // we only walk the right path once
  walkRight = false;

  // visit the left sublist
  printSublists(numbers, sublist.subList(1, sublist.size()), n, walkRight, level+1);
}

И это вывод:

[1, 3]
[4]
[4, 0]

Answer 3

вероятно, вам нужно будет что-то сделать таким образом -

public static void printSublists(ArrayList numbers, ArrayList sublist, int n,
        int i) {

    if (sublist.sum() == n) {
        System.out.println(sublist.toString());
        sublist.removeAll(sublist);//added remove all here
    } 
    else {
        //for (int j = 0; j < numbers.size(); j++) {//commented this line
        while(i<number.size()){//need while loop
            sublist.add(numbers.get(i));
            printSublists(numbers, sublist, n, ++i);//i+1 changed to ++i
            //sublist.remove(numbers.get(i));// commented here
        }
    }
}

Answer 4

В вашем коде для цикла:

        for (int j = 0; j < numbers.size(); j++) {
            sublist.add(numbers.get(i));
            printSublists(numbers, sublist, n, i + 1);
            sublist.remove(numbers.get(i));
        }

Переменная j никогда не используется. То есть вы постоянно повторяете одно и то же, и я серьезно сомневаюсь, что вы хотите это сделать.