[backtracking method] backtracking method to solve the problem of Full Permutation

• subject ： Give an array without duplicate numbers nums , Return all possible permutations . You can return the answers 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]]
  Topic link ：https://leetcode-cn.com/problems/permutations/

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        n = len(nums)
        def backtracking(nums, n):
            if len(path) == n:
                res.append(path[:])
                return
            for i in range(n):
 				 #  Because there are no duplicate elements , So just judge that the current element is  
 				 #  No in path Array , no need used Array 
                if nums[i] not in path:
                    path.append(nums[i])
                    backtracking(nums, n)
                    path.pop()
                else:
                    continue
                
        backtracking(nums, n)
        return res

• subject 2： Given a sequence that can contain repeating numbers nums , In any order Returns all non repeating permutations .
• Example 1：
  Input ：nums = [1,1,2]
  Output ：[[1,1,2],[1,2,1],[2,1,1]]
  Topic link ：https://leetcode-cn.com/problems/permutations-ii/

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtracking(nums, used):
            if len(path) == len(nums):
                res.append(path[:])
                return 

            for i in range(len(nums)):
                if used[i]: 
                    continue
                if i >= 1 and  nums[i] == nums[i-1] and not used [i-1]:
                    continue
                used[i] = 1
                path.append(nums[i])
                backtracking(nums, used)
                path.pop()
                used[i] = 0
            
        res = []
        path = []
        nums.sort()
        # used  Initialization is zero , meaning ： stay nums No element in the array is used 
        # used = [1, 0, 1,]  meaning ：nums[0],nums[2] Already in use  
        used = [0 for i in range(len(nums))]
        backtracking(nums, used)
        return res

• This full permutation problem and the previous subset , The combination problem is the same , You don't need to weigh them together , Remove the weight together .
  The whole arrangement is also , Because it is a full permutation, the traversal of each layer is to traverse the whole nums Array , If nums No repetition of elements in , Then we just need to judge the new nums[i] Is it already in path in , But for those with repeating elements nums, We need a new one used Array to determine whether the number has been used .
  Be careful ： After these questions, we must pay attention to , When you go up on each floor , Be sure to correct the original nums Array to sort , Put the same elements together .

About python Built in full arrangement , Composite library

• product The cartesian product 　　（ There is a sampling arrangement to put back ）
  Namely nums Elements in can be reused

• permutations array 　　（ Do not put the sampling arrangement back ）
  nums The element in cannot be reused

• combinations Combine , No repetition 　　（ Don't put the sampling combination back ）
  nums The element in cannot be reused

• combinations_with_replacement Combine , Repeat 　　（ Sampling combination with return ）
  nums Elements in can be reused

The professional explanation still depends on the official ：https://docs.python.org/3.10/library/itertools.html

"""  Each function has two arguments ,  The first is the iteratable object ,  The second is to extract from the iteratable objects   array   or   Combine   Number of elements of  """

import itertools
# lis  No repeating elements 
lis = ['a', 'b', 'c']
#  There is a sort of put back （ Elements can be reused ）
for i in itertools.product(lis, repeat=2):
    print(i, end=' ')
"""  There is a sort of put back （ Elements can be reused ）: ('a', 'a') ('a', 'b') ('a', 'c') ('b', 'a') ('b', 'b') ('b', 'c') ('c', 'a') ('c', 'b') ('c', 'c') """

#  No put back sort （ Elements cannot be reused ）
for i in itertools.permutations(lis, 2):
    print(i, end=' ')
"""  No put back sort （ Elements cannot be reused ）: ('a', 'b') ('a', 'c') ('b', 'a') ('b', 'c') ('c', 'a') ('c', 'b') """


#  No put back combination （ Elements cannot be reused ）
for i in itertools.combinations(lis, 2):
    print(i, end=' ')
"""  No put back combination （ Elements cannot be reused ）: ('a', 'b') ('a', 'c') ('b', 'c') """

#  There are put back combinations （ Elements can be reused ）
for i in itertools.combinations_with_replacement(lis, 2):
    print(i, end=' ')
"""  There are put back combinations （ Elements can be reused ）: ('a', 'a') ('a', 'b') ('a', 'c') ('b', 'b') ('b', 'c') ('c', 'c') """


# lis2  There are repeating elements in it 
lis2 = ['a', 'a', 'c']
#  There is a sort of put back （ Elements can be reused ）
for i in itertools.product(lis2, repeat=2):
    print(i, end=' ')
"""  There is a sort of put back （ Elements can be reused ）: （ This a Most of them are for explanation , The output sequence has been adjusted ） ('a', 'a')（ first a The subscript is 0 Of a, the second a The subscript is 0 Of a） ('a', 'a')（ first a The subscript is 0 Of a, the second a The subscript is 1 Of a） ('a', 'a')（ first a The subscript is 1 Of a, the second a The subscript is 0 Of a） ('a', 'a')（ first a The subscript is 1 Of a, the second a The subscript is 1 Of a） ('a', 'c') ('a', 'c') （ It's similar to the above ） ('c', 'a') ('c', 'a') ('c', 'c') """
#  No put back sort （ Elements cannot be reused ）
for i in itertools.permutations(lis2, 2):
    print(i, end=' ')
"""  No put back sort （ Elements cannot be reused ）: ('a', 'a') ('a', 'c') ('a', 'a') ('a', 'c') ('c', 'a') ('c', 'a') """
#  No put back combination （ Elements cannot be reused ）
for i in itertools.combinations(lis2, 2):
    print(i, end=' ')
"""  No put back combination （ Elements cannot be reused ）: ('a', 'a') ('a', 'c') ('a', 'c') """
#  There are put back combinations （ Elements can be reused ）
for i in itertools.combinations_with_replacement(lis2, 2):
    print(i, end=' ')
"""  There are put back combinations （ Elements can be reused ）: ('a', 'a') ('a', 'a') ('a', 'c') ('a', 'a') ('a', 'c') ('c', 'c') """