0046._Permutations.md

46. Permutations

难度:Medium

刷题内容

原题连接

• https://leetcode.com/problems/permutations/

内容描述

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]
]

思路1 - 时间复杂度: O(n!n)- 空间复杂度: O(n)*****

很不错的考察递归的一道题，每次都将第一个和之后的数交换即可。

class Solution {
public: 
   vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > ans;
        if(!nums.size())
            return ans;
        if(nums.size() == 1)
            ans.push_back(nums);
        for(int i = 0;i < nums.size();++i)
       {
            swap(nums[0],nums[i]);
            vector<int> v(nums.begin() + 1,nums.end());
            vector<vector<int> > ret = permute(v);
            for(int i = 0;i < ret.size();++i)
            {
                ret[i].push_back(nums[0]);
                ans.push_back(ret[i]);
            }
            swap(nums[0],nums[i]);
        }
        return ans;
    }
};

思路2 - 时间复杂度: O(n!)- 空间复杂度: O(n)******

我们可以对上面的算法进行优化，用DFS的方法，每次记录已经搜索过的数字进行递归即可

class Solution {
public: 
void DFS(int* visited,vector<int>& nums,vector<vector<int> >& ans,vector<int> temp)
{
    int count1 = 0;
    for(int i = 0;i < nums.size();++i)
        if(!visited[i])
        {
            temp.push_back(nums[i]);
            visited[i] = 1;
            DFS(visited,nums,ans,temp);
            temp.pop_back();
            visited[i] = 0;
            count1 = 1;
        }
    if(!count1)
        ans.push_back(temp);
}
vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > ans;
        int visited[nums.size()];
        memset(visited,0,sizeof(visited));
        vector<int> temp;
        for(int i = 0; i < nums.size();++i)
        {
            visited[i] = 1;
            temp.push_back(nums[i]);
            DFS(visited,nums,ans,temp);
            temp.pop_back();
            visited[i] = 0;
        }
        return ans;
    }
};