【LeetCode每天一题】Permutations(排列组合)

佚名 6年前 (2019-04-14) 随笔 1010人围观抢沙发百度已收录

Given a collection of distinct integers, return all possible permutations.

Example:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
思路
　　对于排列组合问题首先应该想到使用递归思想来解决。另外还有一种非递归的解决办法。

解决代码

　　递归方式
　　 图示步骤

解决代码

 1 class Solution(object):  2     def permute(self, nums):  3         """
 4  :type nums: List[int]  5  :rtype: List[List[int]]  6         """
 7         if not nums:  8             return []  9         res = [] # 设置最终结果集 10  self.permution(nums, res, []) 11         return res 12     
13     def permution(self,nums, res_list, path): 14         if not nums: # 如果nums为空，则说明元素已经组合完毕，并将结果保存在结果集中(递归结束条件) 15  res_list.append(path) 16             return
17         for i in range(len(nums)): # 递归循环，nums[:i]+nums[i+1:] 表示将第nums[i]个元素加入到path中，在对剩下的元素进行递归。 18             self.permution(nums[:i]+nums[i+1:], res_list, path+[nums[i]])

循环方式
 思路：主要思路是从一个元素开始，然后对其进行排列，然后第二个元素到来之后就变成两个元素进制排列。依此类推，当循环完毕之后，所有的元素就组合完毕。
 图示步骤：

解决代码

 1 class Solution(object):  2     def permute(self, nums):  3         """
 4  :type nums: List[int]  5  :rtype: List[List[int]]  6         """
 7         res = [[]] # 设置一个空列表  8         for n in nums: # 从第一个元素开始遍历  9             tem_list = [] # 辅助列表，存储当前元素n和res中的列表的组合结果 10             for i in res: # 遍历res列表中每一种组合 11                 for j in range(len(i)+1): # 求出res中每一个列表的长度并加一(为了对当前n进行重组). 12                     tem_list.append(i[:j]+[n]+i[j:]) # 将当前n和res中的每一个列表进行重组。 13             res = tem_list # 赋值 14         return res      # 返回结果