46. 全排列

方法1

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        int n = nums.size();
        helper(ret, nums, 0, n);
        return ret;
    }

    void helper(vector<vector<int>>& ret, vector<int>& nums, int i, int n){
        if(i==n){
            ret.push_back(nums);
            return;
        }

        for(int j=i; j<n; j++){
            swap(nums, i, j);
            helper(ret, nums, i+1, n);
            swap(nums, i, j);
        }
    }

    void swap(vector<int>& nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

方法2

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
public:
    void backtracking(vector<int>& nums, vector<bool>& used){
        if(path.size()==nums.size()){
            result.push_back(path);
            return;
        }

        for(int i=0; i<nums.size(); i++){
            if(used[i]==true)
                continue;

            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};