Find all permutations of a string in C++
You may need to remove duplicates. Consider what your output will be if, for example, your input string is "aaa".



Code like this is unusual:

// nextList contains an array of empty strings
nextList[i*string.length+j] += SubString(prevList[i],0,j);


IMO this would be more usual:

// nextList is empty
// calculate new string
string nextString = SubString(prevList[i],0,j)
    + string[0]
    + SubString(prevList[i],j,string.length-1);
nextList.Add(nextString);




Returning by value is sometimes necessary but can be inefficient. Your algorithm creates many temporary List objects. A better API might be ...

void Permute(const String&amp; inputString, List&amp; outputList) { ... }


... where one empty List is allocated by the caller, and you add to it.



This statement may be incorrect ...

List prevList = Permute(SubString(string,1,string.length));


... I don't know how returns the string 'string[i...j)' is defined but perhaps this statement should be ...

List prevList = Permute(SubString(string,1,string.length - 1));




You may run out of memory very quickly. For a string of length n there are n! ('n factorial') permutations. "what's up doc?" has 14 characters => 87178291200 (or 0x144C3B2800) i.e. bigger than 232 combinations.