46. Permutations

[goungoun]

Intuition

I've learned permutation at high school. It is how we organize elements with the order variation.

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

Based on the index, iterate through the input I can decide what to choose. First come gets more options.

• idx 0: There are three options to choose the element. Any number within the array is ok. You have 3 choices.
• idx 1: Exclude the first choice. I can choose the other two elements. You have 2 choices.
• idx 2: Exclude the first and second choice. No choice, I have to choose the last one. You have only one choice.

The past choices are impacting the later choices like our life, the number of possible outcome is 3 x 2 x 1 = 6, it is 3!.

Assumption

The problem is tagged medium, but I can see that it is intentionally designed simple and within control.

Constraints:

• 1 <= nums.length <= 6 The maximum length of the array is not that long. So, 6 x 5 x 4 x 3 x 2 x 1 = 720. If the code has to perform recursive calls, it is within the range without causing stack overflow error.
• All the integers of nums are unique. I will use it to improve its performance.

There is a reason to strictly restrict the length to 6 to compute permutation and the current problem is combination.

image: https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time

Approach

I used tmp array list to track its context while doing recursive calls from dfs helper function.

Steps:

1. Pick one of the nums and add it to a tmp list.
2. Go down to a deeper level and select another one and add it to a tmp list.
3. If tmp is filled with all numbers, append it to the result list.
4. Go back where it was and remove the value to prepare next iteration.

Example:

  nums = [1,2,3]
  level 0:             [1]           [2]            [3]
  level 1:       [1,2] [1,3]      [2,1] [2,3]     [3,1] [3,2]
  level 2:     [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

  return [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Issue

The code is as below, the issue is that the output becomes with the empty list [[],[],[],[],[],[]].

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret = []
        tmp = []
       
        def dfs():
            if len(tmp) == len(nums):
                print(f"tmp={tmp}") # Debug
                ret.append(tmp)
                return

            for i in range(len(nums)):
                #print (f"i={i}, nums[i]={nums[i]}")
                if nums[i] not in tmp:
                    tmp.append(nums[i])
                    #print(f"tmp={tmp}")
                    dfs()
                    tmp.pop()

        dfs()

        return ret

I put print(f"tmp={tmp}") to debug the issue, the output shows the results as below. It looks that the algorithm itself does not have the problem. It comes from something else handling the nested structure of the list.

Stdout:

tmp=[1, 2, 3]
tmp=[1, 3, 2]
tmp=[2, 1, 3]
tmp=[2, 3, 1]
tmp=[3, 1, 2]
tmp=[3, 2, 1]

Solution

tmp is a list. When it is append to another list ret, the reference is appended to ret rather than a copy of its value. Consequently, later modifications of tmp like popping elements during the backtracking process also affect the versions of tmp already stored. This leads to the result list being filled with references to an empty list after the recursive function executes.

To put the implication into consideration:
ret.append(tmp) should be ret.append(tmp.copy()) or ret.append(tmp[:]).

Performance

I also concerned about its performance. The length of the array is short, 1 <= nums.length <= 6, element selection from an index may impact too much though, technically the time complexity is increasing O(n * n!) due to if nums[i] not in tmp. So, I also added tmp_set = set() additionally. It is only applicable given the constraints in the problem, "All the integers of nums are unique."

tmp = []
tmp_set = set() # According to the constraint, all the integers of nums are unique.

for n in nums:
    if n not in tmp_set:
        tmp.append(n)
        tmp_set.add(n)
        dfs() # tmp is maintained as a context during the recursive call!
        tmp.pop()
        tmp_set.remove(n)

See also:
The technique to combine different data structures to improve the performance is previously used to solve another problem.
380. Insert Delete GetRandom O(1) Design/random_set.py

Complexity

Bruth-Force(full branching):

• Time complexity: O(n**n)
• Space complexity: O(n**n)

Backtracking(w/pruning):

• Time complexity: O(n*n!)
• Space complexity: O(n) for recursion stack, O(n*n!) for output.

Backtracking(w/pruning, tmp_set):

• Time complexity: O(n*n!)
• Space complexity: O(n) for recursion stack, O(n*n!) for output.

Conclusion

Use backtracking when a sequence of objects is chosen from a specified set. - by Richard E. Neapolitan (Foundations of Algorithms 5th edition)

code:
https://github.com/goungoun/leetcode/blob/main/BackTracking/permutations.py

[goungoun]

By the way, python has the built-in function for permutations. Just import and one line return code.

from itertools import permutations
return list(permutations(nums))