CareerCup

The problem can be solved in 2^n time and space.
Keep on finding the subsets of the array. While finding the subsets calculate the sum. if the sum matches then add the subset in a different List. finally print the list.

that is of too much running time... and also repetitions will come... I don't know the exact solution ,but what we can do is , we should sort the arry. then we can discard all the numbers above the required number.. now with the subset we got , we should proceed.. don't know how to approach later...and definitely it can be solved in better time..

have a look!!

public static void main(String[] args){

Scanner in = new Scanner(System.in);
System.out.println("Give the set size");
int set_size = in.nextInt();

System.out.println("Give the numbers");
int[] nums = new int[set_size];
int[] flag = new int[set_size];
int i =0;

while(i<set_size){

nums[i] = in.nextInt();
flag[i] = 0;
i++;
}

System.out.println("Enter the sum for which combination of numbers have to be find out");
int sum = in.nextInt();

num_combo_sum(nums,flag,sum,0);




}

static void num_combo_sum(int[] nums, int[] flag, int sum, int index){

int len = nums.length;
int i =index;
while(i<len){

if(flag[i]!=1){
if(nums[i]==sum){

flag[i]=1;
int j =0;
while(j<nums.length){
if(flag[j]==1)
System.out.print(nums[j]+" ");
j++;
}
System.out.println();
flag[i]=0;

}

else if(nums[i]>sum)
;
else{
flag[i]=1;
num_combo_sum(nums, flag, sum - nums[i],i+1);
flag[i] =0;
}

}

i++;
}
}

public class PrintAllCombi {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int s = 6;
		int[] a = new int[] {2,3,6,7,8};
		getCombi(a, 0, s, 0, "");
	}
	
	private static void getCombi(int[] a, int j, int s, int currentSum, String st) {
		if(s == currentSum) {
			System.out.println(st);
			return;
		}
		if(currentSum > s) {
			return;
		}
		for(int i=j; i<a.length; i++) {
			getCombi(a, i, s, currentSum+a[i], st+"+"+a[i]);
		}
	}

}

At least test the program before posting it online ...

if the set has only positive integers it can be solved using dp. I m just posting the code for number of such scoring ways.if needed use a list to store the scoring modes

# include<stdio.h>
# include<stdlib.h>
 
int main(){
        int a[]={2,3,6,7,8},netsum=0,i,j,*table;
        for(i=0;i<5;i++)
                netsum+=a[i];
        table=(int *)calloc(netsum+1,sizeof(int));
        table[0]=1;
        for(j=0;j<5;j++)
                for(i=a[j];i<=netsum;i++)
                        table[i]+=table[i-a[j]];
        for(i=0;i<=netsum;i++)
                printf("%d ",table[i]);
        return 0;
}

Coin change problem.
Instead of printing(storing) only optimal solution print(store) all possible solution.

<pre lang="" line="1" title="CodeMonkey67513" class="run-this">/*
My idea is simple...
Takes '7' as an example:
7 can be:
0 + 7 or
1 + 6 or
2 + 5 or
3 + 4

Then we just do it my dynamic programming.
However, a problem is that:
2 + 5 = 2 + 2 + 3
3 + 4 = 3 + 2 + 2
They are the same answer!!

My solution is:
recording the answer by "the number of elements we used."
For example, suppose we have {1, 2, 3} as an input and the int we want to compose is '7'.
Then we record [0, 2, 1] as a possible answer which is:
1 * 0 + 2 * 2 + 3 * 1.
The way I checking for duplicate is that I convert this record to an unique char* which is "0@2@1" and put it input a list<char*>.
Then use the "sort()" and "unique()" of c++ STL list to help me eliminate the duplicate....

Well... I know this is a stupid answer..... But it is all I have....
*/





map<int, list<int*> > solved;

list<int*> findCombination(int * set, int l_set, int point) {
list<int*> my_sols;
if (point == 0) return my_sols;

list<int*> head_sols;
list<int*> tail_sols;
for (int head = 0 ; head <= point/2 ; head++) {
if (solved.find(head) != solved.end())
head_sols = (*solved.find(head));
else head_sols = findCombination(set, l_set, head, ...);

if (solved.find(point-head) != solved.end())
tail_sols = (*solved.find(point-head));
else tail_sols = findCombination(set, l_set, point-head, ...);
}

if (head_sols.size() == 0) return tail_sols;
if (tail_sols.size() == 0) return head_sols;

list<char*> strs_my_sols;

list<int*>::iterator head_iter;
list<int*>::iterator tail_iter;
for (head_iter = head_sols.begin() ; head_iter != head_sols.end() ; head_iter++) {
int * new_sol = (int*) malloc(sizeof(int)*l_set);
memcpy(new_sol, (*head_iter), sizeof(int)*l_set);
for (tail_iter = tail_sols.begin() ; tail_iter != tail_sols.end() ; tail_iter++) {
for (int i = 0 ; i < l_set ; i++) {
new_sol[i] += (*tail_iter)[i];
}
}

// make answer string
string new_answer;
for (int i = 0 ; i < l_set ; i++) {
new_answer.append(itoa(new_sol[i]));
new_answer.append("@");
}
free(new_sol);

strs_my_sols.push(new_answer.c_str());
}

// sort and unique
strs_my_sols.sort();
strs_my_sols.unique();

// convert from string type answer to int* type
list<char*>::strs_iter;
for (strs_iter = strs_my_sols.begin() ; strs_iter != strs_my_sols.end() ; strs_iter++) {
int * new_sol = (int*) malloc(sizeof(int)*l_set));
char *tok = strtok((*strs_iter), "@");
new_sol[0] = atoi(tok);
for (int i = 1 ; i < l_set ; i++) {
tok = strtok(NULL, "@");
new_sol[i] = atoi(tok);
}
my_sols.push(new_sol);
}

solved.push(point, my_sols);

return my_sols.push(new_sol);
}


int main (int argc, char *argv[]) {
/*
I omitted the IO code for getting inputs.
Suppose "set" is an int array for the candidate numbers.
Suppose "l_set" is an int for the length of "set."
Suppose "point" is an int which we want to find out the combination.
*/

list<int*> sols = findCombination(set, l_set, point);

list<int*>::iterator sols_iter;
for (sols_iter = sols.begin() ; sols_iter != sols.end() ; sols_iter++) {
string str_answer;
for (int i = 0 ; i < (l_set) ; i++) {
for (int j = 0 ; j < (*sols_iter)[i] ; j++) {
str_answer.append(itoa(set[j]));
str_answer.append("+");
}
}
char *char_answer = str_answer.c_str();
char_answer[str_answer.length()] = (char)0;
char_answer[str_answer.length()-1] = (char)0;
cout << char_answer << endl;
}

return 0;
}</pre><pre title="CodeMonkey67513" input="yes">
</pre>

dynamic programming solution:
opt(i,n) = opt(i-1,n)+opt(i-1,n-a[i]).

Assuming the points are stored in the array a in sorted order.
then opt(i,n) is the number of ways of scoring n points using first i points.

its so simple ...same coin denomination problem but little diference

#define MAX_POINT 4
#define ARR_SIZE 100
#include <stdio.h>

/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);

/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int arr[ARR_SIZE],int n, int i)
{

/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
// static int arr[ARR_SIZE];

if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= MAX_POINT; k++)
{
arr[i]= k;
printCompositions(arr,n-k, i+1);
}
}
}

/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
int i,flag=1;

for (i = 0; i arr[i+1]) flag=0;
if(flag)
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}

/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 and 3 of %d are\n", n);
int arr[ARR_SIZE]={1,2,3,4};
printCompositions(arr,n, 0);
getchar();
return 0;
}

@putta.sreenivas did u selected or not..??? & in where its asked india or us..??

please reply

standard knapsack problem

If we have a set of coins, a1,a2,...ak, what preparations should be done so that the function S(N) = number of different changes with a1,a2,...ak could be calculated in CONST time (independent on N)? :-)

No need DP, a modified DFS will do.

void PrintRecord(const vector<int>& donom, const vector<int>& record, int start)
{
for(int i = start; i >= 0; i--)
for(int j = 0; j < record[i] ; j++)
cout << donom[i] << " ";
cout << endl;
}

void PrintAllExchanges(const vector<int>& donom, int start, int value, vector<int>& record)
{

if( start >= donom.size() || value < 0)
return;

int count = 0;
//DFS
while( value >= 0)
{
record[start] = count;
if( value == 0 ){
PrintRecord(donom, record, start);
return;
}

PrintAllExchanges(donom, start+1, value, record);
value -= donom[start];
count++;
}
}

int main()
{
vector<int> donom;
donom.push_back(3);
donom.push_back(2);

donom.push_back(6);
donom.push_back(7);
donom.push_back(8);

vector<int> record(donom.size(),0);
PrintAllExchanges(donom, 0, 14, record);
}

I would say, try it by sorting array, memoization, and backtrack.

backtrack would prune the recursion tree wherever appropriate ie.Sum(set)>required then backtrack.
memoization would store the values of lower subtrees, so they arent called again
sorting will improve backtrack performance.eg. once you backtrack from nth element, you dont need to worry about n+1th since Arr[n]<arr[n+1]

although to put this mathematically into big0 is a bit challenging.

int ref[] = {2,3,6,7,8};
void printcombination(int n,int index,int i)
{
static int a[100];
int j;
if (n == 0)
{
for(j=0;j<index;j++)
printf("%d ",a[j]);
printf("\n");
}
else if(n>0)
{
for(j=i;j<5;j++)
{
a[index]=ref[j];
printcombination(n-ref[j],index+1,j);
}
}
}
main()
{
int n;
printf("enter value of n :");
scanf("%d",&n);
printcombination(n,0,0);
}

int ref[] = {2,3,6,7,8};
void printcombination(int n,int index,int i)
{
static int a[100];
int j;
if (n == 0)
{
for(j=0;j<index;j++)
printf("%d ",a[j]);
printf("\n");
}
else if(n>0)
{
for(j=i;j<5;j++)
{
a[index]=ref[j];
printcombination(n-ref[j],index+1,j);
}
}
}
main()
{
int n;
printf("enter value of n :");
scanf("%d",&n);
printcombination(n,0,0);
}

A typical DP problem.

- for calculating sum(n), i assume sum(0) to sum(n-1) are already calculated.

every sum is treated as a state. To reach a new state, calculate from all the previous possible states.

DP formulation

void merge( set<string> &s1, set<string> &s2 ) {
	set<string>::iterator sIter;
	for (sIter = s1.begin(); sIter != s1.end(); ++sIter)
		s2.insert(*sIter);
}

void merge( set<string> &s1, string s, set<string> &s2 ) {
	s.append("+");
	string stemp(s);
	set<string>::iterator sIter;
	for (sIter = s1.begin(); sIter != s1.end(); ++sIter) {
		s.clear();
		s.append(stemp);
		s.append(*sIter);
		s2.insert(s);
	}
}

string get_string( int i ) {
	stringstream out;
	out << i;
	return out.str();
}

//PRINT ALL COMBINATIONS OF COIN CHANGE
void All_combinations( int target, int *list, int n ) {
	sort(list, list+n);

	set<string> sSet;
	vector<set<string>> row(target+1);
	vector<vector<set<string>>> combination(n+1,row);

	vector<set<string>> prev;
	vector<set<string>> curr;

	sSet.insert("-2");
	row.push_back(sSet);
	int i, k;

	for (i=1; i<=target; ++i) {
		sSet.clear();
		for (k=1; k<=n; ++k) {
			curr = combination[k];
			prev = combination[k-1];
			if (k>1)
				merge(prev[i], sSet);

			if ((i-list[k-1])>0){
				merge(curr[i-list[k-1]], get_string(list[k-1]), sSet);
			}
			else if (i==list[k-1])
				sSet.insert(get_string(i));

			curr[i] = sSet;
			combination[k] = curr;
		}
	}

	set<string>::iterator sIter;
	cout<<"combinations\n";
	//target = 4;
	//n = 3;
	i=0;
	for (sIter = combination[n][target].begin(); sIter != combination[n][target].end(); ++sIter) {
		i++;
		cout<<*sIter<<endl;
	}
	cout<<i<<"combinations"<<endl;

}