46. Permutations

problem description

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

algorithm thought

我第一遍做的算法：

得到所有排列，和之前组合数相加得到target很像。这里直接使用回溯法，加上一个位置数组，区分是否已经加入新组合。

第二遍做的算法：

得到所有排列问题，也是我们算法课将回溯法的一个例题。直接每次交换两个数字，将所有情况都交换一遍，就是所有排列。其实也可以用递归的思想解释问题。首先将一个数字交换到index 0位置，那么之后的所有位置又可以递归调用函数，得到后面位置的所有排列。第一位置补上，就是所有排列了

code

//first time
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> mark(nums.size(),false);
        vector<vector<int>> res;
        vector<int> tmp;
        per(nums,res,tmp,mark);
        return res;
    }
    void per(vector<int>& nums,vector<vector<int>>& res,vector<int> tmp,vector<bool>& mark){
        if(tmp.size()==nums.size()){
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();++i){
            if(mark[i]==false){
                mark[i]=true;
                tmp.push_back(nums[i]);
                per(nums,res,tmp,mark);
                tmp.pop_back();
                mark[i]=false; 
            }
        }
    }
};

//second
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        per(nums,res,0,nums.size());
        return res;
    }
    void per(vector<int>& nums,vector<vector<int>>& res,int i,int j){
        if(i==j-1){
            res.push_back(nums);
            return ;
        }
        for(int k=i;k<j;++k){
            swap(nums[i],nums[k]);
            per(nums,res,i+1,j);
            swap(nums[i],nums[k]);
        }
    }
};

algorithm thought

对于第一个算法：回溯法时间复杂度是O(2^n)，但是这里应该不用那么久，遍历到后期，很多数中的数组都已经被加入，只需要直接continue；所以，这个算法还是不慢的

对于第二个算法：得出所有的排列，类似枚举法，一共需要执行n!次。每次时间复杂度是O(1)。最后时间复杂度就是O(n!).