Сравнение времени выполнения — аналогичный код выполняется в 4 раза медленнее

Я решаю проблему с разделением палиндрома, которая требует вернуть все разделы палиндрома данной строки (http://oj.leetcode.com/problems/palindrome-partitioning/). Я нашел два решения этой проблемы. Мне трудно понять, почему существует огромное различие во времени выполнения этих двух подходов:

(Предполагать bool isPal() заданная функция, которая сообщает, является ли данная строка палиндромом или нет за время O (длина)

1-е решение: (использует возврат):

void find(string s, int start, vector<string> &r, vector<vector<string> > &res){
if (start >= s.size()){
res.push_back(r);
}else{
for (int i=start;i<s.size();i++){
if (isPal(s.substr(start, i-start+1))){
r.push_back(s.substr(start,i-start+1));
find(s,i+1,r,res);
r.pop_back();
}
}
}
}

vector<vector<string>> partition(string s) {
vector<vector<string> > res;
vector<string> r;
find(s,0,r,res);
return res;
}

2-е решение:

vector<vector<string> > partition(string s) {
vector<vector<string> > answer;

if(s.size() == 0)
return answer;

// if s is Palindrome, push to answer
if(isPal(s))
answer.push_back(vector<string>(1,s));

if(s.size() == 1)
return answer;

for(int i=1; i<s.size(); ++i) {
string s1 = s.substr(0, i);
string s2 = s.substr(i, s.size()-i);

if(isPal(s1)) {
// get sub_answers of partition(s[i:])
vector<vector<string> > sub_answer = partition(s2);

// add s1 to the begin of sub_answers
for(int j=0; j<sub_answer.size(); ++j) {
sub_answer[j].insert(sub_answer[j].begin(), s1);
answer.push_back(sub_answer[j]);
}
}
}
return answer;
}

Хотя оба решения имеют одну и ту же основную идею, первое решение работает в 108ms, в то время как второй занимает 472ms время. Это из-за теоретической неэффективности (возможно, второе решение решает одну проблему несколько раз) или из-за неэффективной реализации (некоторые концепции C ++)?
Пожалуйста, укажите причину неэффективности второго решения.

Заметка: Оба решения верны и дают одинаковый результат.