【LeetCode with Python】 47. Permutations II

题目

原题页面:https://leetcode.com/problems/permutations-ii/
本文地址:http://leetcode.xnerv.wang/permutations-ii/
题目类型:Backtracking
难度评价:Medium
类似题目:(M) Next Permutation, (M) Permutations, (M) Palindrome Permutation II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].


分析

与Permutations在处理上的唯一区别是,对于重复元素,不去尝试调换,而是直接skip,避免出现重复的排列。


代码

class Solution:
    def doPermuteUnique(self, num_list):
        if 1 == len(num_list):
            return [ num_list ]
        res_list = [ ]
        for i in range(0, len(num_list)):
            if i > 0 and num_list[0] == num_list[i]:
                continue
            num_list[0], num_list[i] = num_list[i], num_list[0]
            sub_res_list = self.doPermuteUnique(num_list[1:])
            list_head = [ num_list[0] ]
            new_list = [ list_head + list for list in sub_res_list]
            res_list.extend(new_list)
        return res_list

    # @param num, a list of integer
    # @return a list of lists of integers
    def permuteUnique(self, num):
        num.sort()
        return self.doPermuteUnique(num)

results matching ""

    No results matching ""