【LeetCode】0047 全排列II

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

# -*- coding:utf-8 -*-

class Solution(object):
    def permuteUnique1(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)]
        output_final = []
        backtrack(0, flag_list)
        for each in output:
            if each not in output_final:
                output_final.append(each)
        return output_final
if __name__ == '__main__':
    nums = [1, 1, 2]
    print(Solution().permuteUnique1(nums))

思路：这道题我甚至犹豫要不要写这个笔记2333。虽然我知道出题人不是这个意思，但是在上一道题后面加个去重就行。

其实排序一下剪枝就行了，多一个位置记录上一次处理的值，一样剪枝跳过就行，但是不写了x