LeetCode 46. Permutations

Description

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

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

描述

給定一組不同的整數(shù)，返回所有可能的排列。

思路

遞歸

• 寫好遞歸函數(shù)的要點(diǎn)是：1.確定遞歸關(guān)系式 2. 確定遞歸結(jié)束條件 3.A問題可以分解成B,C,D···Z幾個(gè)子問題，假設(shè)子問題已經(jīng)解決，在此情況下來解決A問題
• 此題目中，假設(shè)有一個(gè)數(shù)組A[10],我們拿出A[1],假設(shè)A[1:10](兩端的值都可以取到)組成的所有序列都已經(jīng)取到，我們把A[1]和所有的組合相加，就得到了
• 以A[1]為首的所有可能組合
• 同理，我們把A[2]拿出來，把A[1]+A[3:10]組成一個(gè)新的數(shù)組，假設(shè)此數(shù)組的所有排列組合和已經(jīng)取到，再把A[2]和它們相加，就得到了以A[2]為首的所有組合

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 遞歸返回條件：只有一個(gè)值，直接返回
        if len(nums) == 1:
            return [nums]
        # 聲明最終需要返回的答案
        res = []
        # 遍歷數(shù)組中的元素
        for i, num in enumerate(nums):
            # 去掉已經(jīng)遍歷的元素
            subnum = nums[:i]+nums[i+1:]
            # 去掉元素nums[i],假設(shè)子問題subnum的所有組合已經(jīng)拿到，把num[i]和所有可能的組合相加，得到結(jié)果
            for subres in self.permute(subnum):
                res.append([num]+subres)
        # 返回
        return res

源代碼文件在這里
?本文首發(fā)于何睿的博客，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來源，作者信息和本聲明.