Все возможные комбинации для суммирования до заданного числа с использованием заданного набора чисел

Question

Найденное решение

Поиск всех возможных комбинаций чисел для достижения заданной суммы

Вопрос

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

Как манипулировать приведенным ниже алгоритмом, чтобы получить все возможные комбинации, включая повторяющиеся числа, для суммирования до заданного значения?

import java.util.ArrayList;
import java.util.Arrays;

class SumSet
{
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial)
    {
        int s = 0;
        for (int x : partial)
            s += x;
        if (s == target)
            System.out.println("sum(" + Arrays.toString(partial.toArray()) + ")=" + target);
        if (s >= target)
            return;
        for (int i = 0; i < numbers.size(); i++)
        {
            ArrayList<Integer> remaining = new ArrayList<Integer>();
            int n = numbers.get(i);
            for (int j = i + 1; j < numbers.size(); j++)
                remaining.add(numbers.get(j));
            ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
            partial_rec.add(n);
            sum_up_recursive(remaining, target, partial_rec);
        }
    }

    static void sum_up(ArrayList<Integer> numbers, int target)
    {
        sum_up_recursive(numbers, target, new ArrayList<Integer>());
    }

    public static void main(String args[])
    {
        Integer[] numbers = { 3, 9, 8, 4, 5, 7, 10 };
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)), target);
    }
}

И вывод не должен содержать Перестановки итолько Комбинации .

Пример

15 можно суммировать с помощью 3 + 3 + 3 + 3 + 3 и 9 + 3 + 3.Однако вывод должен содержать только одно из следующих значений: 9 + 3 + 3 или 3 + 9 + 3 или 3 + 3 + 9

Answer 1

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

    import java.util.ArrayList;
    import java.util.Arrays;

    public class SumSet
    {
        static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial)
        {
            int s = 0;
            for (int x : partial)
                s += x;
            if (s == target)
                System.out.println("sum(" + Arrays.toString(partial.toArray()) + ")=" + target);
            if (s >= target)
                return;
            for (int i = 0; i < numbers.size(); i++)
            {
                int n = numbers.get(i);
                ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
                partial_rec.add(n);
                sum_up_recursive(numbers, target, partial_rec);
            }
        }

        static void sum_up(ArrayList<Integer> numbers, int target)
        {
            sum_up_recursive(numbers, target, new ArrayList<Integer>());
        }

        public static void main(String args[])
        {
            Integer[] numbers = { 3, 9, 8, 4, 5, 7, 10 };
            int target = 15;
            sum_up(new ArrayList<Integer>(Arrays.asList(numbers)), target);
        }
    }
and the results allow for repetition as you wished:

    sum([3, 9, 3])=15
    sum([3, 8, 4])=15
    sum([3, 4, 3, 5])=15
    sum([3, 4, 8])=15
    sum([3, 4, 4, 4])=15
    sum([3, 4, 5, 3])=15
    sum([3, 5, 3, 4])=15
    sum([3, 5, 4, 3])=15
    sum([3, 5, 7])=15
    sum([3, 7, 5])=15
    sum([9, 3, 3])=15
    sum([8, 3, 4])=15
    sum([8, 4, 3])=15
    sum([8, 7])=15
    sum([4, 3, 3, 5])=15
    sum([4, 3, 8])=15
    sum([4, 3, 4, 4])=15
    sum([4, 3, 5, 3])=15
    sum([4, 8, 3])=15
    sum([4, 4, 3, 4])=15
    sum([4, 4, 4, 3])=15
    sum([4, 4, 7])=15
    sum([4, 5, 3, 3])=15
    sum([4, 7, 4])=15
    sum([5, 3, 3, 4])=15
    sum([5, 3, 4, 3])=15
    sum([5, 3, 7])=15
    sum([5, 4, 3, 3])=15
    sum([5, 5, 5])=15
    sum([5, 7, 3])=15
    sum([5, 10])=15
    sum([7, 3, 5])=15
    sum([7, 8])=15
    sum([7, 4, 4])=15
    sum([7, 5, 3])=15
    sum([10, 5])=15

Редакция: выше содержит перестановки (в отличие от комбинаций).Если кто-то хочет избежать получения [3, 5, 7] и [3, 7, 5] и той же комбинации 4 другими способами, можно также настаивать на том, чтобы число не уменьшалось (или, что эквивалентно, не увеличивалось) [если вы хотите быть математиком, вы можете добавить слово «монотонный»].Это можно сделать с помощью быстрой проверки в верхней части рекурсивной функции, используя небольшой метод, адаптированный из принятого ответа в (Java) Проверочный массив для увеличения элементов .Пересмотренная версия становится:

import java.util.ArrayList;
import java.util.Arrays;

public class SumSet
{
    public static boolean isNondecreasing(ArrayList<Integer> arr)
{
    for(int i=1; i<arr.size();i++)
    {
        if(arr.get(i-1)>arr.get(i))
            return false;
    }
    return true;
 }

    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial)
    {
        int s = 0;
        if (!(isNondecreasing(partial))){
            return;
        }
        for (int x : partial)
            s += x;
        if (s == target)
            System.out.println("sum(" + Arrays.toString(partial.toArray()) + ")=" + target);
        if (s >= target)
            return;
        for (int i = 0; i < numbers.size(); i++)
        {
            int n = numbers.get(i);
            ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
            partial_rec.add(n);
            sum_up_recursive(numbers, target, partial_rec);
        }
    }

    static void sum_up(ArrayList<Integer> numbers, int target)
    {
        sum_up_recursive(numbers, target, new ArrayList<Integer>());
    }

    public static void main(String args[])
    {
        Integer[] numbers = { 3, 9, 8, 4, 5, 7, 10 };
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)), target);
    }
}

, и результат является более кратким:

sum([3, 3, 3, 3, 3])=15
sum([3, 3, 9])=15
sum([3, 3, 4, 5])=15
sum([3, 4, 8])=15
sum([3, 4, 4, 4])=15
sum([3, 5, 7])=15
sum([4, 4, 7])=15
sum([5, 5, 5])=15
sum([5, 10])=15
sum([7, 8])=15