All possible combinations to sum up to a given number using given set of numbers

Question

Found Solution

Finding all possible combinations of numbers to reach a given sum

Question

In the above solution, it is possible to get all the combinations without repeating the same number using given set of numbers to sum up to the given value.

How to manipulate the algorithm below to get all possible combinations including repetitive numbers to sum up to the given value?

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);
    }
}

And output should not contain Permutations and only Combinations.

Example

15 can be summed up by 3 + 3 + 3 + 3 + 3 and 9 + 3 + 3. However output should only contain one of following, 9 + 3 + 3 or 3 + 9 + 3 or 3 + 3 + 9

Answer 1

Just remove the work it is doing to get the remaining numbers and pass back in the original numbers when you recurse. I tested the below.

    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

Revision: The above contains permutations (as opposed to combinations). If one wants to avoid geting [3, 5, 7] and [3, 7 , 5] and the same combination 4 other ways, too, one can insist the number be non-decreasing (or, equivalently, non-increasing) [if you want to be math-y, you could throw in the word "monotonic"]. This can be done with a quick check at the top of the recursive function, using a little method adapted from the accepted answer at (Java) Check array for increasing elements. The revised version becomes:

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);
    }
}

and the output is the terser:

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