C++ : Recursion based implementation


#1
vector<vector<int>> res;

void backtrack(vector<int> t, vector<int> &A, int *visited) {
    int f = 0;
    for(int i=0; i<A.size(); i++) {
        if(visited[i]==0) {
            f = 1;
            break;
        }
    }
    if(f == 0) {
        res.push_back(t);
        return;
    }
    for(int i=0; i<A.size(); i++) {
        if(!visited[i]) {
            int tp = A[i];
            visited[i] = 1;
            t.push_back(tp);
            backtrack(t, A, visited);
            visited[i] = 0;
            t.pop_back();
        }
    }
}

vector<vector<int>> Solution::permute(vector<int> &A) {
    vector<int> t;
    int n = A.size();
    res.clear();
    if(n==0) return res;
    int visited[n];
    memset(visited, 0, n * sizeof(int));
    backtrack(t, A, visited);
    return res;
}