【LeetCode】0046 全排列

https://leetcode-cn.com/problems/permutations/

# -*- coding:utf-8 -*-
class Solution(object):
    def permute(self, nums):
        def backtrack(i, flag_list, temp_list=[]):
            if i == n:
                output.append(temp_list)
                return
            # 找到第一个可用数字
            for j in range(len(flag_list)):
                if flag_list[j] != 0:
                    flag_list[j] = 0
                    temp_list.append(nums[j])
                    backtrack(i + 1, flag_list[:], temp_list[:])
                    flag_list[j] = 1
                    temp_list = temp_list[:-1]
        n = len(nums)
        output = []
        flag_list = [1 for _ in range(n)]
        backtrack(0, flag_list)
        return output
if __name__ == '__main__':
    nums = [1, 2, 3]
    print(Solution().permute1(nums))

思路：回溯法，首先选择一个数字，然后向下递归下一位和当前可选数字，如果满足条件就添加到输出列表中，然后回溯，回溯的操作包括将使用标记从0变为1，将当前临时结果列表中剔除最后一个数字。

思考：有一个不用标记列表的方法，就是向后交换，因为是交换，也省去了临时列表等空间，但是实际提交和上一个方法相比较，空间上并没有区别，反而是时间上有了区别，我也不是很懂为啥。

使用交换来模拟每次寻找可用数字，举个例子，1，2，3，4这个列表，如果我们处理第一位时，1，2，3，4都是可用数字，因此我们可以用1分别与后面的数字进行交换，这样idx0就分别取到了所有数字。当固定了1时，我们继续分析2，3，4，依然是交换，这样可以固定新的idx0（也就是旧列表的idx1），以此类推。

    def permute1(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        def backtrack(first=0):
            if first == n:
                output.append(nums[:])
            for i in range(first, n):
                # 这里使用交换来模拟递归其余数字（比如1,2,3。 交换1 2   13  就模拟了第一个位置的全部可能）
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]

        n = len(nums)
        output = []
        backtrack()
        return output