leetcode--46--全排列

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

示例:

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

题目链接：https://leetcode-cn.com/problems/permutations

思路：
1、采用广度优先搜索的思路，先假设全排列里只用了一个元素，然后再迭代的加入其他的元素，每次加入元素时分别对之前的全排列的结果在所有位置均可插入当前元素
2、需要注意的是需要考虑添加元素时不能改变原来的结果，因此使用深拷贝来进行备份

Python代码

import copy

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        if not nums:
            return []

        ret = [[nums[0]]]

        for i in range(1,len(nums)):
            item = nums[i]
            ret_cp = copy.deepcopy(ret)    // 深拷贝上一轮的返回值，避免对原始值产生修改
            curr = []
            for ls in ret_cp:
                for j in range(len(ls)+1):
                    ls_cp = copy.deepcopy(ls)   // 深拷贝
                    ls_cp.insert(j, item)
                    curr.append(ls_cp)
            ret,curr = curr,ret
    
        return ret

C++代码：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        if(nums.empty()){
            return {};
        }
        vector<vector<int>> ret;
        vector<int> curr;
        curr.push_back(nums[0]);
        ret.push_back(curr);

        for(int i=1; i<nums.size(); i++){
            int item = nums[i];
            vector<vector<int>> ret_cp(ret);
            vector<vector<int>> temp;
            for(auto ls:ret_cp){
                for(int j=0; j<=ls.size(); j++){
                    vector<int> ls_cp(ls);
                    ls_cp.insert(ls_cp.begin()+j, item);
                    temp.push_back(ls_cp);
                }
            }
            ret.swap(temp);
        }
        return ret;
    }
};