Leetcode47 全排列 II

2020年9月18日 0 作者 折纸

题目描述

file

方法一

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        check = [0 for i in range(len(nums))]

        def traceback(path,nums,check):
            if( len(path) == len(nums)):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if check[i] == 1:
                    continue
                if i>0 and nums[i] == nums[i-1] and check[i-1] == 0: #相同元素的第一个还未被使用时则不使用该元素 剪枝
                    continue

                check[i] = 1
                traceback(path+[nums[i]],nums,check)
                check[i] = 0

        traceback([],nums,check)
        return res

 

思路

  • 剪枝条件:

    • 对应位置的数已被使用过
    • 有相同元素的情况下,最左边的相同元素尚未被使用时剪枝
  • 终止条件:

    • len(path) == len(nums) 相当于找到了一个排列