LeetCode-递归回溯-全排列-两题

46.全排列

CODE

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums)<2:
            return [nums]
        result = []

        def subsort(nums , begin):
            if len(nums) - begin == 2:
                result.append(nums[:])
                tmp = nums[begin] #swap
                nums[begin] = nums[begin+1]
                nums[begin+1] = tmp
                result.append(nums[:])
            else:
                for i in range(begin,len(nums)):
                    tmp = nums[begin] #swap
                    nums[begin] = nums[i]
                    nums[i] = tmp
                    subsort(nums[:] , begin+1)
            return

        subsort(nums,0)
        return result
        
执行用时 :32 ms , 在所有 Python3 提交中击败了 99.58% 的用户
内存消耗 :12.6 MB, 在所有 Python3 提交中击败了 99.47% 的用户

分析与总结

在写代码时候要注意python的函数参数传递机制。

函数参数传递机制问题在本质上是调用函数（过程）和被调用函数（过程）在调用发生时进行通信的方法问题。基本的参数传递机制有两种：值传递和引用传递。

• 值传递（passl-by-value）过程中，被调函数的形式参数作为被调函数的局部变量处理，即在堆栈中开辟了内存空间以存放由主调函数放进来的实参的值，从而成为了实参的一个副本。值传递的特点是被调函数对形式参数的任何操作都是作为局部变量进行，不会影响主调函数的实参变量的值。
• 引用传递(pass-by-reference)过程中，被调函数的形式参数虽然也作为局部变量在堆栈中开辟了内存空间，但是这时存放的是由主调函数放进来的实参变量的地址。被调函数对形参的任何操作都被处理成间接寻址，即通过堆栈中存放的地址访问主调函数中的实参变量。正因为如此，被调函数对形参做的任何操作都影响了主调函数中的实参变量。

结论：python不允许程序员选择采用传值还是传引用。Python参数传递采用的肯定是“传对象引用”的方式。这种方式相当于传值和传引用的一种综合。如果函数收到的是一个可变对象（比如字典或者列表）的引用，就能修改对象的原始值－－相当于通过“传引用”来传递对象。如果函数收到的是一个不可变对象（比如数字、字符或者元组）的引用，就不能直接修改原始对象－－相当于通过“传值”来传递对象。

故在此题中，我们不希望在原始对象上进行修改。就使用了list[:]，先复制一份列表再递归调用。

[47] 全排列 II

#
# @lc app=leetcode.cn id=47 lang=python3
#

#
# https://leetcode-cn.com/problems/permutations-ii/description/
#
# algorithms
# Medium (55.39%)
# Likes:    197
# Dislikes: 0
# Total Accepted:    33.4K
# Total Submissions: 59.2K
# Testcase Example:  '[1,1,2]'
#
# 给定一个可包含重复数字的序列，返回所有不重复的全排列。
# 
# 示例:
# 
# 输入: [1,1,2]
# 输出:
# [
# ⁠ [1,1,2],
# ⁠ [1,2,1],
# ⁠ [2,1,1]
# ]
# 
#

# @lc code=start
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if len(nums)<2:
            return [nums]
        result = []

        nums.sort()

        def subsort(nums , begin):
            if len(nums) - begin == 2:
                result.append(nums[:])
                if nums[begin] == nums[begin+1]:
                    return
                tmp = nums[begin] # swap
                nums[begin] = nums[begin+1]
                nums[begin+1] = tmp
                result.append(nums[:])
            else:
                subsort(nums[:] , begin+1)
                for i in range(begin+1,len(nums)):
                    if nums[begin] == nums[i]:
                        continue
                    tmp = nums[begin] # swap
                    nums[begin] = nums[i]
                    nums[i] = tmp
                    subsort(nums[:] , begin+1)
            return

        subsort(nums,0)
        return result
        
# @lc code=end

思路

采用递归的思路，将nums中的第一个数字固定后递归。这个第一个数字与所有其他数字交换后为一个循环。在最终只剩下两个数字时结束递归，返回输出。

要注意的一点就是有重复数字的情况。当需要交换的两个数字相同是，不再交换，也不进行递归。同时最后两个数相同时，只输出一种情况。

若是ABA的情况，还是会导致重复。故先排序。将相同的情况放在一起。