LeetCode 46.全排列

问题描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

问题分析

• 经典回溯问题

代码实现

python版本

import copy
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        track = []
        index = []
        def backtrack(nums,start,track,index):
            if len(track)==len(nums) and track not in ans:
                ans.append(copy.deepcopy(track))
            for i in range(len(nums)):
                if i not in index:
                    index.append(i)
                    track.append(nums[i])
                    backtrack(nums,i+1,track,index)
                    index.pop(-1)
                    track.pop(-1)
        backtrack(nums,0,track,index)
        return ans

C++版本

class Solution {
public:
    vector<vector<int>>ans;
    void backtrack(vector<int> nums,vector<int>track,vector<int>index){
        int n = nums.size();
        if (track.size() == n && find(ans.begin(),ans.end(),track)== ans.end()){
            ans.push_back(track);
        }

        for (int i=0; i<n; i++){
            if (find(index.begin(),index.end(),i)== index.end()){
                index.push_back(i);
                track.push_back(nums[i]);
                backtrack(nums,track,index);
                index.pop_back();
                track.pop_back();
            }
           
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> track;
        vector<int> index;
        backtrack(nums,track,index);
        return ans;
        
    }
};

回溯算法相当于暴力穷举，所以时间复杂度很高，根据backtrack的调用次数可知时间复杂度为O(n!)。