47. Permutations II

Problem Statement

link: LeetCode.cn LeetCode Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example:

Input: nums = [1,1,2] Output: [[1,1,2],[1,2,1],[2,1,1]]

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solution Approach

Sort the input list and use backtracking with a boolean array to track used elements, ensuring that duplicates are skipped to generate all unique permutations.

Algorithm

1. Sorting: Start by sorting the input list to ensure duplicates are adjacent, making it easier to skip them during permutation generation.
2. Backtracking with Used Tracking: Use a backtracking function with a boolean array to track which elements are already included in the current permutation path.
3. Skipping Duplicates: During the backtracking process, skip adding an element if it’s a duplicate of the previous element and the previous element has not been used in the current recursion level.

Implement

    class Solution:
        def permuteUnique(self, nums: List[int]) -> List[List[int]]:
            nums.sort()
            res = []
            def bt(path, curr):
                if len(path) == len(nums):
                    res.append(path[:])
                for i in range(len(curr)):
                    if i > 0 and curr[i] == curr[i - 1]:
                        continue
                    bt(path + [curr[i]], curr[:i] + curr[i + 1:])
            bt([], nums)
            return res

    
    

Twitter  facebook  Email