#
# @lc app=leetcode.cn id=46 lang=python3
#
# [46] 全排列
#
# https://leetcode-cn.com/problems/permutations/description/
#
# algorithms
# Medium (73.45%)
# Likes:    530
# Dislikes: 0
# Total Accepted:    77.2K
# Total Submissions: 104.3K
# Testcase Example:  '[1,2,3]'
#
# 给定一个没有重复数字的序列，返回其所有可能的全排列。
# 
# 示例:
# 
# 输入: [1,2,3]
# 输出:
# [
# ⁠ [1,2,3],
# ⁠ [1,3,2],
# ⁠ [2,1,3],
# ⁠ [2,3,1],
# ⁠ [3,1,2],
# ⁠ [3,2,1]
# ]
# 
#

# @lc code=start
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        
        check = [0 for i in range(len(nums))]
        self.backtrack([], nums, check)
        
        return self.res
    
    def backtrack(self, sol, nums, check):
        # 回溯三要素1：结果终止符
        if len(sol) == len(nums):
            self.res.append(sol)
            return
        
        for i in range(len(nums)):
            # 回溯三要素2：剪枝
            if check[i] == 1:
                continue
            check[i] = 1
            # 回溯三要素3：回溯
            self.backtrack(sol+[nums[i]], nums, check)
            check[i] = 0     
# @lc code=end

