【算法系列 - LeetCode】给定一个没有重复数字的序列，返回其所有可能的全排列。

[AwesomeDevin]

题目

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

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

思路

1. 传入目标数组arr,定义返回值result=[],第三方遍历tmp=[]
2. 执行函数get(arr,tmp,result)
3. 当tmp数组长度与目标数组arr一致时，将tmp添加到result中，否则，对目标数组arr进行遍历,如果tmp中不存在arr[index],则将arr[index]添加到tmp中
4. 之后使用get(arr,tmp,result)进行递归,递归时需要使用tmp.pop()来保证每轮递归中的tmp长度不变,发生变化的只是tmp的下标值
5. 传递tmp参数需要进行deepcopy，这样下一轮的tmp才会保留本轮添加的arr[index],否则返回值为[[],[],[],[],...]

JS实现

function main(arr){
	var result = []
	get(arr,[],result)
	return result
}

function get(arr,tmp,result){
	if(tmp.length === arr.length)     //tmp与参数的数组长度相同时，push到result中
	{
		result.push(tmp)
		return
	}
	for(var index in arr)
	{
		if(!tmp.includes(arr[index]))
		{
			tmp.push(arr[index])
			get(arr,JSON.parse(JSON.stringify(tmp)),result)    //tmp需要进行深deepclone,否则会出现子数组长度为0
			tmp.pop()
		}
	}
}

Python实现

#coding=utf-8
import copy

def get(arr,tmp,result):
    if len(tmp) == len(arr):
        result.append(tmp)
        return
    for item in arr:
        if item not in tmp:
            tmp.append(item)
            # tmp1 = tmp
            get(arr,copy.deepcopy(tmp),result)
            tmp.pop()


def main(arr):
    result = list()
    get(arr,[],result)
    return result

if __name__ == "__main__":
    print(main([1,2,3]))