Python solution with detailed explanation


  • 0
    G

    Solution

    Permutations II https://leetcode.com/problems/permutations-ii/

    Standard Backtracking Pattern

    • Sketch a recursion tree diagram for [1,1,2]. The ith level of this tree generates the ith index of the permutation. Therefore, the candidates for the ith level must be unique, otherwise we will have duplicate recursive calls and will end up with duplicate permutations.
    • https://goo.gl/photos/CRd9mLPZ92L28VWr8
    class Solution(object):
        def permuteUnique(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            result = []
            self.helper(nums, [], len(nums), result)
            return result
        
        def helper(self, nums, so_far, N, result):
            if len(so_far) == N:
                result.append([x for x in so_far])
            else:
                candidates, cpos = set([]), {}
                for idx, x in enumerate(nums):
                    if x not in candidates:
                        candidates.add(x)
                        cpos[x] = idx
                for c in candidates:
                    so_far.append(c)
                    nnums = nums[:cpos[c]] + nums[cpos[c]+1:]
                    self.helper(nnums, so_far, N, result)
                    so_far.pop()
            return
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.