0%

【LeetCode with Python】 46. Permutations

题目

原题页面:https://leetcode.com/problems/permutations/
本文地址:</permutations/>
题目类型:Backtracking
难度评价:Medium
类似题目:(M) Next Permutation, (M) Permutations II, (M) Permutation Sequence, (M) Combinations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].


分析

一道递归回溯的题目,所以跟大多数递归回溯题目类似的解法。只有一点值得注意一下,由于需要从一个集合中挑选出元素,然后下一次递归从剩余的元素中继续挑选,所以必须能够记忆和区分出当前已经选出了哪些元素。这里的做法是每次把选择的元素与当前列表中第一个元素交换,然后将除第一个元素外的子列表传递给下一次递归作为其需要处理的当前列表。
另外,a collection of numbers也许是暗示了集合中不会有重复元素?至少对比(M) Permutations II看来,本题的原意应该是没有重复元素的。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def doPermute(self, num_list):
if 1 == len(num_list):
return [ num_list ]
res_list = [ ]
for i in range(0, len(num_list)):
num_list[0], num_list[i] = num_list[i], num_list[0]
sub_res_list = self.doPermute(num_list[1:])
list_head = [ num_list[0] ]
new_list = [ list_head + list for list in sub_res_list]
res_list.extend(new_list)
return res_list

# @param num, a list of integer
# @return a list of lists of integers
def permute(self, num):
return self.doPermute(num)