46. Permutations

O(n*n!) time

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        do {
            res.push_back(nums);
        } while (next(nums));
        return res;
    }

    bool next(vector<int> &A) {
        int n = A.size();
        int x = 0, y = 0;
        for (int i = n - 1; i > 0; --i) {
            if (A[i - 1] < A[i]) {
                x = i - 1;
                y = i;
                break; // 说明从i开始后边全降序
            }
        }
        if (y == 0) return false;
        for (int i = n - 1; i > x; --i) {
            if (A[i] > A[x]) {
                swap(A[i], A[x]); // 找到下一个比A[x]大的开始下一轮遍历
                break;
            }
        }
        reverse(A.begin() + y, A.end());
        return true;
    }
};

backtracking O(n*n!) time

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n, res = len(nums), []
        def dfs(A, b):
            if b == n:
                res.append(A)
                return
            for i in range(b, n):
                A[i], A[b] = A[b], A[i]
                dfs(A[:], b + 1)
        dfs(nums, 0)
        return res

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n, res = len(nums), []
        def dfs(b):
            if b == n:
                res.append(nums[:])
                return
            for i in range(b, n):
                nums[i], nums[b] = nums[b], nums[i]
                dfs(b + 1)
                nums[i], nums[b] = nums[b], nums[i]
        dfs(0)
        return res

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(begin(nums), end(nums));
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int> nums, int b) { // 这里nums是深拷贝！！
        int n = nums.size();
        if (b == n) {
            res.push_back(nums);
        }
        for (int i = b; i < n; ++i) {
            swap(nums[i], nums[b]); // 每次把一个数放到最前边（可以保证剩下的序列还是升序），然后对剩下的序列全排列
            dfs(nums, b + 1);
        }
    }

    vector<vector<int>> res;
};

O(nⁿ) time

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        visited.resize(n);
        sort(begin(nums), end(nums));
        dfs(nums);
        return res;
    }

    void dfs(const vector<int> &nums) {
        if (v.size() == n) {
            res.push_back(v);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (visited[i]) continue;
            visited[i] = true;
            v.push_back(nums[i]); // 把当前剩下还没访问过的数分别尝试append到v后边
            dfs(nums);
            v.pop_back();
            visited[i] = false;
        }
    }

    int n;
    vector<bool> visited;
    vector<int> v;
    vector<vector<int>> res;
};