[algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
if m getting question correct then
the our task is to Given a total score n, print out all the
combination to compose n.
Examples:
For n = 1, the program should print following:
1
For n = 2, the program should print following:
1 1
2
For n = 3, the program should print following:
1 1 1
1 2
2 1
3
For n = 4, the program should print following:
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
and so on …
Algorithm:
At first position we can have three numbers 1 or 2 or 3.
First put 1 at first position and recursively call for n-1.
Then put 2 at first position and recursively call for n-2.
Then put 3 at first position and recursively call for n-3.
If n becomes 0 then we have formed a combination that compose n, so
print the current combination
so function looks like
void printCompositions(int n, int i)
{
/ 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(n-k, i+1);
}
}
}
Please Correct me if i am wrong or you found for any test case it
failing
Thanks Regards
Shashank The Bets Way To Escape From The Problem is to Solve It
CSE, BIT Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
use DP see careercup.. On Tue, Mar 15, 2011 at 10:43 PM, albert theboss alberttheb...@gmail.comwrote: @bittu : many over lapping sub problems available in ur case ... better try dp to get the efficient solution... @all : suggest algo for the case without repetition. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- DIPANKAR DUTTA M-TECH,Computer Science Engg. EC Dept,IIT ROORKEE Uttarakhand , India – 247667 --- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:dipan...@iitr.ernet.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
@sukhmeet: plz explain ur method if the no is 50 On Sun, Mar 13, 2011 at 8:24 PM, sukhmeet singh sukhmeet2...@gmail.comwrote: I think it can be done like this that assume that the number is represented as 1.. like 4= , 3= 111 ans so on now if u have to fint the total number of ways then it is similar to placing a '+' sign in the mid places Like 3= 1 1 1 so possible are 1+11 (1+2) or 11+1 (2+1) or 1+1+1(1+1+1) hence 3 ways...!! similar approach can be taken .. hence the problem reduces to placing + sign in b/w .. placing 1 '+' , 2 '+' uptill the number it can be formed...!! Correct me if i am wrong..!! On Fri, Mar 11, 2011 at 10:02 PM, saurabh agrawal saurabh...@gmail.comwrote: Do it assuming as two cases. On Fri, Mar 11, 2011 at 9:46 PM, Dave dave_and_da...@juno.com wrote: This is a good place to use recursion. One thing you have to know is whether order matters. E.g., are 2 + 1 and 1 + 2 the same or different ways to represent 3 as a sum of positive integers. This choice will affect the way you write the recursive function. Dave On Mar 11, 9:33 am, saurabh agrawal saurabh...@gmail.com wrote: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
Use DP -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
On Mar 11, 9:33 am, saurabh agrawal saurabh...@gmail.com wrote:
Given an integer n , you have to print all the ways in which n can be
represented as sum of positive integers
I suggest you
1) generate the numeric partitions of n.
That's the lists of numbers in sorted order whose sum is n.
e.g. The numeric partitions of 3 are: {(1,1,1), (1,2), 3}
2) For each partition generate its multiset permutations.
Note: there is a formula for how many of sums of positive integers to
n
there are but I don't what it is.
Regards,
Ralph Boland
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
My approach :
partition(n) =
1 + partition(n-1)
2+partition(n-2)
3+partition(n-3)
..
..
n-1+partition(1)
n
Assuming 1+2 and 2+1 as different.
On Mon, Mar 14, 2011 at 11:53 PM, Aviral Gupta aviral@gmail.com wrote:
you can use coin change problem as one of the solutions.
Regards
Aviral Gupta
http://coders-stop.blogspot.com/
On Mar 14, 8:43 pm, Ralph Boland rpbol...@gmail.com wrote:
On Mar 11, 9:33 am, saurabh agrawal saurabh...@gmail.com wrote:
Given an integer n , you have to print all the ways in which n can be
represented as sum of positive integers
I suggest you
1) generate the numeric partitions of n.
That's the lists of numbers in sorted order whose sum is n.
e.g. The numeric partitions of 3 are: {(1,1,1), (1,2), 3}
2) For each partition generate its multiset permutations.
Note: there is a formula for how many of sums of positive integers to
n
there are but I don't what it is.
Regards,
Ralph Boland
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards,
chinna.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
I think it can be done like this that assume that the number is represented as 1.. like 4= , 3= 111 ans so on now if u have to fint the total number of ways then it is similar to placing a '+' sign in the mid places Like 3= 1 1 1 so possible are 1+11 (1+2) or 11+1 (2+1) or 1+1+1(1+1+1) hence 3 ways...!! similar approach can be taken .. hence the problem reduces to placing + sign in b/w .. placing 1 '+' , 2 '+' uptill the number it can be formed...!! Correct me if i am wrong..!! On Fri, Mar 11, 2011 at 10:02 PM, saurabh agrawal saurabh...@gmail.comwrote: Do it assuming as two cases. On Fri, Mar 11, 2011 at 9:46 PM, Dave dave_and_da...@juno.com wrote: This is a good place to use recursion. One thing you have to know is whether order matters. E.g., are 2 + 1 and 1 + 2 the same or different ways to represent 3 as a sum of positive integers. This choice will affect the way you write the recursive function. Dave On Mar 11, 9:33 am, saurabh agrawal saurabh...@gmail.com wrote: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
This is a good place to use recursion. One thing you have to know is whether order matters. E.g., are 2 + 1 and 1 + 2 the same or different ways to represent 3 as a sum of positive integers. This choice will affect the way you write the recursive function. Dave On Mar 11, 9:33 am, saurabh agrawal saurabh...@gmail.com wrote: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
Do it assuming as two cases. On Fri, Mar 11, 2011 at 9:46 PM, Dave dave_and_da...@juno.com wrote: This is a good place to use recursion. One thing you have to know is whether order matters. E.g., are 2 + 1 and 1 + 2 the same or different ways to represent 3 as a sum of positive integers. This choice will affect the way you write the recursive function. Dave On Mar 11, 9:33 am, saurabh agrawal saurabh...@gmail.com wrote: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
