題目：
給定一個(gè)沒有重復(fù)數(shù)字的序列，返回其所有可能的全排列。

示例:

輸入: [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、采用廣度優(yōu)先搜索的思路，先假設(shè)全排列里只用了一個(gè)元素，然后再迭代的加入其他的元素，每次加入元素時(shí)分別對(duì)之前的全排列的結(jié)果在所有位置均可插入當(dāng)前元素
2、需要注意的是需要考慮添加元素時(shí)不能改變?cè)瓉淼慕Y(jié)果，因此使用深拷貝來進(jìn)行備份

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)    // 深拷貝上一輪的返回值，避免對(duì)原始值產(chǎn)生修改
            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;
    }
};