java使用给定的一组数字将所有可能的组合求和为给定的数字

Question

找到解决方案

Finding all possible combinations of numbers to reach a given sum

问题

在上面的解决方案中，使用给定的一组数字求和到给定的值，可以得到所有组合，而无需重复相同的数字

如何操作下面的算法，以得到所有可能的组合，包括重复的数字，以总结到给定的值

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种相同的组合，你可以坚持数字是非递减的（或者，等价地，非递增的）[如果你想成为数学y，你可以加上“单调”一词]。这可以通过递归函数顶部的快速检查来完成，使用一个从(Java) Check array for increasing elements处接受的答案改编的小方法。 修订后的版本为：

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