CODEWITHSUNDEEP
javaarraysfor-looparraylist
S. N
S. N

Reputation: 3959

find all possible combination of a value in an int array

I have a array list with sorted increasing numbers. I have a target value and I must find all the possible combination of the target value within my array. So if I have array = [1,1,3,5,6,7] and my target value is 8 then the program hould should calculate this: 

1+1+6 =8
1+7 = 8
1+7 = 8
3 + 5 = 8,

it should return 4.

here is my implementation for this:

public static int numberOfConnections(int[] e, int b){
        int result = 0;
        int temp = 0;
        for(int i = 0; i < e.length; i++){
            for(int j = 0; j < e.length; j++){
                temp += e[j];
                if(temp > b){
                    temp = 0;
                }
                else if( temp == b){
                    result++;
                    temp = 0;
                }
                else if(temp < b && i == edges.size()){
                    result++;
                }
            }
        }
        return result;
    }

what am I doing wrong ?? I am getting wrong results.

Upvotes: 0

Views: 1608

Answers (2)

Christian St.
Christian St.

Reputation: 1921

If you don't want to use a recursive strategy, you can work with an int array and one boolean array of the same size used as a bitmap.

The boolean array tells your program, which of the values in the int array should exist in the actual calculation.

Taking the example in your question, this can be done as follows:

Values = [1, 1, 3, 5, 6, 7]

Bitmap = Selected Values = 8

(110010) = 1 + 1 + 6 = 8

(100001) = 1 + 7 = 8

(010001) = 1 + 7 = 8

(001100) = 3 + 5 = 8

This will produce in the examples case 2^values.length = 64 different combinations.

!!! EDIT !!!

I was interested, if my idea will result in success, so here's my try:

public static void main(String[] args) {
    int[] values = { 1, 1, 3, 5, 6, 7 };
    int target = 8;

    for (int i = 0; i < (int) Math.pow(2, values.length); i++) {
        boolean[] bitmap = createBitmap(i, values.length);
        int result = calculateResult(values, bitmap);
        if (result == target) {
            System.out.printf("%s = %d\n", 
                getSumString(values, bitmap),
                result);
        }
    }
}

private static boolean[] createBitmap(int value, int arrayLength) {
    boolean[] bits = new boolean[arrayLength];

    int actual;
    for (int i = bits.length - 1; i >= 0; i--) {
        actual = getValue(bits);
        if (actual == value)
            break;
        else if (actual + (int) Math.pow(2, i) <= value)
            bits[i] = true;
    }

    return bits;
}

private static int getValue(boolean[] bits) {
    int value = 0;
    for (int i = bits.length - 1; i >= 0; i--)
        if (bits[i])
            value += (int) Math.pow(2, i);

    return value;
}

private static int calculateResult(final int[] values, boolean[] used) {
    int sum = 0;
    for (int i = 0; i < used.length; i++)
        if (used[i])
            sum += values[i];
    return sum;
}

private static String getSumString(int[] values, boolean[] used) {
    String sumString = "";
    for (int i = 0; i < used.length; i++)
        if (used[i])
            sumString += values[i] + " ";
    return sumString;
}

Executing the main() method results in

3 5 = 8

1 1 6 = 8

1 7 = 8

1 7 = 8

So I think this is a right approach :-)

Upvotes: 3

MeNa
MeNa

Reputation: 1487

Some mistakes:

1) In the internal loop you should not start from 0, but from i+1. otherwise, you counting the same node twice.

2) you checking only combinations of 2, not more! You need a recursive method.

Upvotes: 1

Related Questions