Popular Posts

Monday, February 7, 2011

Powerset or Combination problem

Given an array containing both positive and negative numbers.Program to find the set of elements whose sum is equal to given number
Ex :  array is : { -1, 2, -3, 4, 5, 6 };
sum : 5

Java code :
public class PowerSetProblem {

private static final int size = 6;
private static int[] arr = { -1, 2, -3, 4, 5, 6 };

static void generate_powerset(int[] temparr, int level, int start, int k) {
int i, j;
for (i = start; i < size; i++) {
temparr[level] = arr[i];

int sum = 0;

for (j = 0; j <= level; j++)

sum += temparr[j];

if (sum == k) {
for (j = 0; j <= level; j++)
System.out.print(" " + temparr[j] + " ");
System.out.println();
}
if (i < size - 1)
generate_powerset(temparr, level + 1, i + 1, k);
}
}

public static void main(String[] args) {
int[] temparr = new int[size];
generate_powerset(temparr, 0, 0, 5);
}

}

problem2 :finding two elements whose sum is equal to given umber Algorithm 1) Sort all the elements of the array. 2) Find the index of first positive element, this is initial value of right index r. 3) Initialize: left index l = r – 1. min_sum = INT_MIN 4) In a loop, look for the candidates by comparing sum with minimum sum. If arr[l] + arr[r] becomes negative then increment the right index r, else decrement left index l. refer :http://geeksforgeeks.org/?p=4034

No comments:

Post a Comment