Permutation

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

Solution: Depth First Search

We can use one array to store the current state, we also need another array to check if number is visited to prevent duplication.

The termination condition is straightforward, we just need to check if current state array's size is equal to the size of the input array.

To move forward to next state, we need to consider all numbers from the array. Only need to prcess numbers we haven't visited.

Time Complexity is: O(n!) factorial

void backtrack(vector<int> &arr, vector<int> &num, vector<bool> &visited, vector<vector<int>> &ans) {
    // 1. Termination case
    if (arr.size() == num.size()) {
        ans.push_back(arr);
        return;
    }

    // 2. Try every possible cases
    for (int i=0; i<num.size(); i++) {
        // 3. Check if solution is viable
        if (visited[i]) continue;

        // 4. Move to next state
        arr.push_back(num[i]);
        visited[i] = true;

        // 5. Recursively check next state
        backtrack(arr, num, visited, ans);

        // 6. Roll back to previous state
        arr.pop_back();
        visited[i] = false;
    }   
}

vector<vector<int> > permute(vector<int> &num) {
    vector<vector<int>> ans;
    vector<int> arr;
    vector<bool> visited(num.size(), false);
    backtrack(arr, num, visited, ans);
    return ans;
}

Solution: Swapping numbers

void permuteDFS(int start, vector<int> &num, vector<vector<int> > &res) {
    if (start >= num.size()) res.push_back(num);
    for (int i = start; i < num.size(); ++i) {
        swap(num[start], num[i]);
        permuteDFS(start + 1, num, res);
        swap(num[start], num[i]);
    }
}

vector<vector<int> > permute(vector<int> &num) {
    vector<vector<int> > res;
    permuteDFS(0, num, res);
    return res;
}

Solution:

    vector<vector<int> > permute(vector<int> &num) {
        if (num.empty()) return vector<vector<int> >(1, vector<int>());

        vector<vector<int> > res;
        int first = num[0];
        num.erase(num.begin());
        vector<vector<int> > words = permute(num);
        for (auto &a : words) {
            for (int i = 0; i <= a.size(); ++i) {
                a.insert(a.begin() + i, first);
                res.push_back(a);
                a.erase(a.begin() + i);
            }
        }   
        return res;
    }