46. Permutations

46. Permutations

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> temp;
        int num [6]{ 0 };
        backTrack(nums, ret, temp, num);
        return ret;
    }
private:
    void backTrack(vector<int>& nums, vector<vector<int>>& ret, vector<int>& temp, int* num)
    {
        if(temp.size() == nums.size())
            ret.push_back(temp);
        for(size_t i = 0; i < nums.size(); ++i)
        {
            if(num[i]) continue;
            num[i] = 1;
            temp.push_back(nums[i]);
            backTrack(nums, ret, temp, num);
            temp.pop_back();
            num[i] = 0;
        }
    }
};

去除visited数组

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        backTrack(nums, ret, nums.size(), 0);
        return ret;
    }
private:
    void backTrack(vector<int>& nums, vector<vector<int>>& ret, int length, int index)
    {
        if(index == length)
        {
            ret.push_back(nums);
            return;
        }
        for(int i = index; i < length; ++i) // 这里必须是index而不是index+1，因为index表示这个位置可以保留不动
        {
            // 将后面的数换过来，表示这个位固定为后面换过来的那个数，index之后的数都属于候选池，这样子的话每一位都可以具备所有选择。
            // 对于后面的位来说，他具备获得前面位的能力，因为前面位换到这个位是它可以保持i==index，就获得了前面那个数。
            // 最终的结果就是每一位都具备获得所有数字的能力
            swap(nums[index], nums[i]); 
            backTrack(nums, ret, length, index + 1);
            swap(nums[index], nums[i]);
        }
    }
};