Skip to content

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;
    }
};


回到顶部