The basic idea is that for every position of the string, you fill it
with all possible alphabets in your set of allowed alphabets, let the
set be called alphabet.
Now, you can do this recursively.
backtrack(s,l) denotes, a string s has been formed, and is of length
l. Now we need to add more letters to it. If l is equal to the maximum
length, then you just print the string s, and return.
Otherwise, append the characters available to you. For example, if in
the current scenario, the call is backtrack("po",2), and alphabet =
{'o','p'} and maxlen=3, then we can append 'o' and 'p' to the string
"po", and hence call backtrack("poo",3) and backtrack("pop",3).
You start the process by calling backtrack("",0), and setting maxlen
and alphabet to the appropriate values.
On Fri, Aug 5, 2011 at 12:42 PM, Kamakshii Aggarwal
<[email protected]> wrote:
> @gaurav:i could not understand ur sol.can u explain it again..
>
> On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani <[email protected]>
> wrote:
>>
>> On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
>> <[email protected]> wrote:
>> > given a set of letters and a length N, produce all possible output.(Not
>> > permutation). For example, give the letter (p,o) and length of 3,
>> > produce
>> > the following output(in any order you want, not just my example order)
>> >
>> > ppp ppo poo pop opp opo oop ooo
>> >
>> > another example would be given (a,b) and length 2
>> >
>> > answer: ab aa bb ba
>> >
>> > --
>> > Regards,
>> > Kamakshi
>> > [email protected]
>>
>> This can be done easily by backtracking
>>
>> void backtrack(string s, int l)
>> {
>> if(l == maxlen) { cout<<s<<endl; return; }
>>
>> s.push_back('-');
>> for(int i=0;i<alphabet.size();i++)
>> {
>> s[l]=alphabet[i];
>> backtrack(s,l+1);
>> }
>> }
>>
>> --
>> Gaurav Menghani
>>
>> --
>> 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.
>>
>
>
>
> --
> Regards,
> Kamakshi
> [email protected]
>
> --
> 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.
>
--
Gaurav Menghani
--
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.
