Let us assume you have sum S. The possible numbers it is made up are { 1,
2, .., S }.
Now, for every number belonging to the set, you have two options.
1. Subtract currently chosen number from the given set to sum.
2. Choose next number.
The state will be defined as (num, sum), where num is the number you are
using and sum is current sum.
Recurrence will be,
f (num, sum) = f (num - 1, sum) + f (num, sum - num)
f (num, 0) = 1
f (0, sum) = 0
The translation to code is fairly obvious, which reduces to O (N^2) time
and O (N^2) space dp.
// Code.
int memo [55][505];
int
solve (int num, int sum) {
// f (num, sum) = f (num - 1, sum) + f (num, sum - num)
if (sum == 0) return 1;
if (sum < 0 || num <= 0) return 0;
if (memo [num][sum] != -1) return memo [num][sum];
return memo [num][sum] = solve (num - 1, sum) + solve (num, sum - num);
}
int
main () {
memset (memo, -1, sizeof (memo));
for (int i = 0; i <= 10; i++) printf ("%d %d\n", i, solve (i, i));
return 0;
}
Output:
0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42
Assuming, order matter, [i.e. 1 + 2 != 2 + 1], it reduces to simple
take-it or leave-it knapsack. Though this is tangential to your question.
On Sat, Mar 1, 2014 at 9:55 PM, kumar raja <rajkumar.cs...@gmail.com> wrote:
> Given an integer how many number of ways u can partition the number?
>
> e.g. 3 can be written as 3,1+2,1+1+1
> and 4 can be written as 4, 1+1+1+1,2+2,1+3,1+1+2
>
> So for 3 --> 3
> for 4 -->5.
>
> The order of the elements in the partition does not matter.
> So how to calculate the number of ways to partition the given number?
>
> Can someone give idea on how to write the recurrence relation
> for the problem?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
