leetcode46全排列c++

题目描述

给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

代码实现

方法1：动态规划的思想
若是知道 [0~n-1] 的全排列 C = [[C1],[C2],[C3]…]，可以知道，[0 ~ n]的全排列为将 n 插入C中，插入C1有n+1种插入方法，C2,C3…都是n+1种插入方法。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> tem1,tem2;
        if(!nums.size()) return ans;
        tem1.push_back(nums[0]);
        ans.push_back(tem1);
        for(int i = 1; i < nums.size(); i++){
            int len = ans.size();
            while(len){
                tem1 = ans[--len];
                ans.erase(ans.begin()+len);
                int j = i+1;
                while(j--){
                    tem2 = tem1;
                    tem2.insert(tem2.begin()+j,nums[i]);
                    ans.push_back(tem2);
                }
            }
        }
        return ans;
        
    }
};

方法2：回溯法
递归的思想，[0 ~ n] 的全排列可以看做：交换第一个位置与后面所有位置的数当做固定的第一个数，然后后面的数排列。这就可以用回溯法的方式。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        int len = nums.size();
        back(0,len,nums,ans);
        return ans; 
    }
    void back(int first, int n, vector<int>& nums, vector<vector<int>>& ans){
        if(first == n) ans.push_back(nums);
        for(int i = first; i < n; i++){
            swap(nums, i, first);
            back(first+1,n,nums,ans);
            swap(nums, i, first);
        }
    }
    void swap(vector<int>& nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
};