46.md

46. Permutations

Leetcode link

解题思路

求一组元素可能的排列组合，最常用的方法就是回溯 backtracking 了

为了减少时间复杂度，我们用了一个数组 visited 来记录当前选择的元素是否已经被选过了，达到剪枝的目的

C++

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<bool> visited(nums.size());
        
        getPermutations(res, nums, visited, {});
        return res;
    }
    
    void getPermutations(vector<vector<int>> &res, vector<int>& nums, vector<bool> &visited, vector<int> array) {
        if(array.size() == nums.size()) {
            res.push_back(array);
            return;
        }
        for(int i=0;i<nums.size();i++) {
            if(visited[i]) {
                continue;
            }
            array.push_back(nums[i]);
            visited[i] = true;
            getPermutations(res, nums, visited, array);
            array.pop_back();
            visited[i] = false;
        }
    }
};

Javascript

var permute = function(nums) {
    let res = [];
    let visited = new Array(nums.length).fill(false);
    getPermutations(res, nums, visited, []);
    
    return res;
};

var getPermutations = function(res, nums, visited, arr) {
    if(arr.length === nums.length) {
        res.push(arr);
        return;
    }
    for(let i = 0;i<nums.length;i++) {
        if(visited[i]) {
            continue;
        }
        arr.push(nums[i]);
        visited[i] = true;
        getPermutations(res, nums, visited, [...arr]);
        arr.pop();
        visited[i] = false;
    }
}