it can be done with O(N * S) time complexity.
where N = number of digits
S = sum
intilize : input[1][j]=0 1<=j <= S
input[j][0]=1 0<=j<=N
now fill table using following recurrence :-
input[i][j] = input[i-1][j] or input[i-1][j-input[i]];
now after creating table...check if input[N][S] == 1
if no then sum cannot be created
or
if yes , find all combination recursively by first not considering input[i]
as part of the subset then considering input[i] as a part of the subset.
On Sat, Aug 25, 2012 at 12:34 AM, amrit harry <[email protected]>wrote:
> find the all possible combination of digits ranging 1 to 9 whose sum is
> 10,
> no digit shud be repeated in any combination.
> 1234
> 127
> 136
> 145
> 19
> 235
> 28
> 37
> 46
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/K9atBSG79wQJ.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
