leetcode-backtracking

47. Permutations II.py

class Solution:
    """
    Problem Clarifcation:
        -There's duplicates in the given array
    Problem formulation
        -We need to return all possible unique permuluation. S
    
    Thought Process:
        -Greedy+Backtracking
        prev: the previous number we put it in the current index. The reason why we need prev variable is we need one more constraint to avoid duplicate result in our answer.
        prev = None
        if visited[i] or prev == nums[i]:
            continue
        -Greedy+Counter
            Idea is at first level we don't pick duplicates number because if picking any of the duplicate numbers as the first number of the permutation 
            would lead us to the same permutation at the end.
    Test Case
           nums = [1,1,2]
           
           []
          / 
        [1] c ={1:1,2:1}
        /  
      [1,1] c ={1:0,2:1}
      /       
    [1,1,2] c ={1:0,2:0}
    
           []
          / 
        [1]
        /   \
      [1,1] [1,2]
      /         \
    [1,1,2] [1,2,1]
          
    Note:
        Because our goal is to return all unique possible solutions. Given array contains duplicates, we will get same result if using the same idea in LC 46, do not take the element that we already picked it up.
    
    Ref:
        1.https://www.youtube.com/watch?v=doQffep-ruo&ab_channel=AlgorithmsCasts
        2.https://www.youtube.com/watch?v=43w8tXWKSLw&ab_channel=basketwangCoding
    """
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
        backtracking + counter hashmap
        
        T: O(n * n!) in worst case, ther's no duplicates in given array.
        """
        def backtrack(a, n, counter):
            if len(a) == n:
                ans.append(a.copy())
                return
            
            # go through our candidate from counter
            for v in counter:
                if counter[v] <= 0:
                    # we could not add this element into our partial solution 
                    continue
                # pick up elemet which counter is not zero
                a.append(v)
                counter[v]-=1
                backtrack(a, n, counter)
                a.pop()
                counter[v]+=1
   
        n = len(nums)
        if n == 0:
            return []
        ans = []
        c = collections.Counter(nums) # take element as key and nb of occurrences as value
        backtrack([], n, c)
        return ans
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
        Implement n-permute-d, d < n.
        T: O(n! * n). we will have P(n,d), where d is n, possibilities. It's n factorial.
        And, we take constant time to progressivly build cur solution.
        S: O(n) because of depth of recuison call( Don't consider output space as extra space)
        """
        ans = []
        def backtrack(cur, n, d, used, cand):
            """
            We assume no dupilcate in given candidate, and we return all uniuqe n-permute-d results.
            """
            if len(cur) == d:
                ans.append(cur.copy())
                return 
            prev = None
            for i in range(n):
                # to avoid take the element that we already pick it up in the same depth
                if used[i] or prev == nums[i]:
                    continue
                cur.append(cand[i])
                used[i] = True
                prev = nums[i]
                backtrack(cur, n, d, used, cand)
                cur.pop()
                used[i] = False
                
        # start with empty list, progressively build possible permutations
        n = len(nums)
        d = n
        used = [False] * n
        # we sort nums in order to avoid get duplicate permutation
        nums.sort()
        backtrack([], n, d, used, nums)
        return ans