Recursion - Combination with in array with no repetition in Java

Question

So I know how to get the size of a combination - factorial of the size of the array (in my case) over the size of the subset of that array wanted. The issue I'm having is getting the combinations. I've read through most of the questions so far here on stackoverflow and have come up with nothing. I think the issue I'm finding is that I want to add together the elements in the combitorial subsets created. All together this should be done recursively

So to clarify:

int[] array = {1,2,3,4,5};

the subset would be the size of say 2 and combinations would be

{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}

from this data I want to see if the subset say... equals 6, then the answers would be: {1,5} and {2,4} leaving me with an array of {1,5,2,4}

so far I have this:

 public static int[] subset(int[] array, int n, int sum){
     // n = size of subsets
     // sum = what the sum of the ints in the subsets should be 

    int count = 0; // used to count values in array later
    int[] temp = new temp[array.length]; // will be array returned

    if(array.length < n){
        return false;
    }

    for (int i = 1; i < array.length; i++) {
        for (int j = 0; j < n; j++) {
            int[] subset = new int[n];
            System.arraycopy(array, 1, temp, 0, array.length - 1); // should be array moved forward to get new combinations

                           **// unable to figure how how to compute subsets of the size using recursion so far have something along these lines**
                            subset[i] = array[i];
                            subset[i+1] = array[i+1];

                            for (int k = 0; k < n; k++ ) {
                               count += subset[k];
                            }
                           **end of what I had **

            if (j == n && count == sum) {
                temp[i] = array[i];
                                    temp[i+1] = array[i+1];
            }
        }
    } subset(temp, n, goal);

    return temp;
}

How should I go about computing the possible combinations of subsets available?

do you want to output one solution or all possible solutions? — Kedarnath Calangutkar
– Kedarnath Calangutkar, Commented Feb 28, 2014 at 1:42
All possible solutions in the form of a singular array as seen as an array with the elements ex: 'array = {1,5,2,4}' which should be returned. Explained above. — user3362954
– user3362954, Commented Feb 28, 2014 at 1:45
And you know how to do it with for-loops, but you do not know how to do it recursively? Or what is your biggest issue? — libik
– libik, Commented Feb 28, 2014 at 1:48
@libik no, the inputted array isn't always sorted. The issue I'm having is getting all permutations, I only ever get the first few. Instead of beating around the bush more... It's the recursive aspect that I am having difficulty with. — user3362954
– user3362954, Commented Feb 28, 2014 at 1:51

libik · Accepted Answer · 2014-02-28 02:33:28Z

1

I hope you will love me. Only thing you have to do is to merge results in one array, but it checks all possibilities (try to run the program and look at output) :) :

public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    int n = 2;
    subset(array, n, 6, 0, new int[n], 0);
}

public static int[] subset(int[] array, int n, int sum, int count, int[] subarray, int pos) {
    subarray[count] = array[pos];
    count++;

    //If I have enough numbers in my subarray, I can check, if it is equal to my sum
    if (count == n) {
        //If it is equal, I found subarray I was looking for
        if (addArrayInt(subarray) == sum) {
            return subarray;
        } else {
            return null;
        }
    }

    for (int i = pos + 1; i < array.length; i++) {
        int[] res = subset(array, n, sum, count, subarray.clone(), i);
        if (res != null) {
            //Good result returned, so I print it, here you should merge it
            System.out.println(Arrays.toString(res));
        }
    }

    if ((count == 1) && (pos < array.length - 1)) {
        subset(array, n, sum, 0, new int[n], pos + 1);
    }

    //Here you should return your merged result, if you find any or null, if you do not
    return null;
}

public static int addArrayInt(int[] array) {
    int res = 0;
    for (int i = 0; i < array.length; i++) {
        res += array[i];
    }
    return res;
}

edited Feb 28, 2014 at 2:33

answered Feb 28, 2014 at 2:28

libik

23.1k10 gold badges52 silver badges94 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user3362954 Over a year ago

Thank you! I will edit appropriately to keep the signature as it was before! Much appreciated. Didn't think of setting the recursive spots where you have them. Must be having a down spell!

Zach Beavon-Collin · Accepted Answer · 2014-02-28 02:01:33Z

0

You should think about how this problem would be done with loops.

for (int i = 0; i < array.length - 1; i++) {
    for (int j = i + 1; j < array.length; j++) {
        if (array[i] + array[j] == sum) {
            //Add the values to the array
        }
    }
}

Simply convert this to a recursive code.

The best way I can think to do this would be to have each recursive call run on a subset of the original array. Note that you don't need to create a new array to do this as you are doing in your code example. Just have a reference in each call to the new index in the array. So your constructor might look like this:

public static int[] subset(int[] array, int ind, int sum)

where array is the array, ind is the new starting index and sum is the sum you are trying to find

answered Feb 28, 2014 at 2:01

Zach Beavon-Collin

2453 silver badges11 bronze badges

2 Comments

Kedarnath Calangutkar Over a year ago

This would only give combinations of 2. But according to the question, n indicates the number of elements in the subsets.

user3362954 Over a year ago

I would very much like to keep the signature on the method and stay with the recursive method and @KedarnathCalangutkar is correct about the 'n' number of elements.

Collectives™ on Stack Overflow

Recursion - Combination with in array with no repetition in Java

2 Answers 2

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related