Permutation

Question

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 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]]

Example 2:

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

Example 3:

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

Solution

Permutation is similar to Subset however we only get the final result

Time Complexity: $O(n!)$

Example: https://leetcode.com/problems/permutations/

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

class App:
    result: List[int]
    frequency: Dict[int, int]
    
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.result = []
        self._permute(nums)
        return self.result

    def _permute(self, nums: List[int], basket: List[int] = []):
        if (len(basket) == len(nums)):
            self.result.append(basket.copy())
            return

        for num in nums:
            if num in basket: continue

            basket.append(num)
            self._permute(nums, basket)
            basket.pop()

In contrast to the Subset > ^473ad2 we're not using for i loop. The reason is we want to pick all the possible numbers in nums without skipping any number. In here we want to choose if num not in basket because we masively add it in.

Permutation duplication

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

In this question, the number could appear multiple time, for example in here number 1 appears twice in nums

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

Using like the previous method wouldn't work because now we are having duplication in nums we can't simply check if num not in tmp anymore - since it could refer to another number (not the same)

Intuition:
The idea is we need keep track of how many numbers we allowed to used. In the example above, we have 2 1's and 1 2's

Next, we need to loop using the frequency this is because now we want to work with the dictionary to group these numbers together. We go through each of the number in the dictionary itself and check if we can use it.

class App:
    result: List[int]
    frequency: Dict[int, int]
    
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.frequency = Counter(nums)
        self.result = []
        self._permute(nums)
        return self.result

    def _permute(self, nums: List[int], basket: List[int] = []):
        if (len(basket) == len(nums)):
            self.result.append(basket.copy())
            return

        for num in nums:
            if self.frequency[num] <= 0: continue

            basket.append(num)
            self.frequency[num] -= 1
            self._permute(nums, basket)
            self.frequency[basket.pop()] += 1

If we loop using the nums itself, it will create duplicated result. For example:

• If we loop through [1,1,2]
  • After the end of 2, we have {1: 0, 2: 1} in the counter and our tmp = [1,1,2], now we're backtracking back
  • We pop 2 out, we have {1: 0, 2: 0}, tmp = [1,1]
  • We pop 1 out, we have {1: 1, 2: 1}, tmp = [1]
  • Now we're at the inital 1, What happens now?
    • Since we have {1: 1, 2: 1} again, it will make [1,1,2] again and put it in the result

Note: difference between this method (using Counter and Subset > Subset duplication) is using counter allows the same element to have different position:

For example, you can have both [2,2,1] and [1,2,2] in the result. Subset > Subset duplication does not allow that