Problem: Print all permutations of a given string
Implementation:
void stringPerm(std::string s, int len, int i = 0)
{
if(i == len)
std::cout<<s<<'\n';
else
{
for(int j = i; j < len; ++j)
{
if(i != j && s[i] == s[j])
continue;
std::swap(s[i], s[j]);
stringPerm(s, len, i + 1);
std::swap(s[i], s[j]);
}
}
}
Complexity: O(n*n!)
Implementation:
void stringPerm(std::string s, int len, int i = 0)
{
if(i == len)
std::cout<<s<<'\n';
else
{
for(int j = i; j < len; ++j)
{
if(i != j && s[i] == s[j])
continue;
std::swap(s[i], s[j]);
stringPerm(s, len, i + 1);
std::swap(s[i], s[j]);
}
}
}
Complexity: O(n*n!)
no need to calculate length each time,it is constant length... can u expalane little bit about back tracking... :)
ReplyDeleteYes, you are right, no need to calculate length each time, can be taken as parameter in the method. I will update the solution.
DeleteThank for mentioning it,