leetcode里, backtracking的time complexity怎么算,比如permutations这题目# JobHunting - 待字闺中
t*r
1 楼
leetcode里, backtracking的time complexity怎么算,比如permutations这题目
class Solution {
public:
void perm(vector num,int k,int n, vector > &res){
if (k==n){
res.push_back(num);
}else{
for (int i=k;i<=n;i++){
int tmp = num[k];
num[k]=num[i];
num[i]=tmp;
perm(num,k+1,n,res);
tmp = num[k];
num[k]=num[i];
num[i]=tmp;
}
}
}
vector > permute(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > res;
perm(num,0,(num.size()-1),res);
return res;
}
};
class Solution {
public:
void perm(vector
if (k==n){
res.push_back(num);
}else{
for (int i=k;i<=n;i++){
int tmp = num[k];
num[k]=num[i];
num[i]=tmp;
perm(num,k+1,n,res);
tmp = num[k];
num[k]=num[i];
num[i]=tmp;
}
}
}
vector
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector
perm(num,0,(num.size()-1),res);
return res;
}
};