# LeetCode46 回溯算法求全排列，这次是真全排列

## 回溯法

class Solution:
def dfs(self, nums, n, i, cur, ret, flag):
if i == n:
ret.append(cur.copy())
return
for p in range(n):
# 遍历所有元素
# 如果p元素已经放置过了，跳过
if flag[p]:
continue
# 当前位置放置p
cur.append(nums[p])
# flag[p]置为True
flag[p] = True
# 递归
self.dfs(nums, n, i+1, cur, ret, flag)
# 回溯
cur.pop()
flag[p] = False

def permute(self, nums: List[int]) -> List[List[int]]:
ret = []
n = len(nums)
# 记录元素i有没有放置过
flag = [False for _ in range(n)]
self.dfs(nums, n, 0, [], ret, flag)
return ret


## 其他方法

class Solution:
def get_next(self, nums: List[int]):
"""
Do not return anything, modify nums in-place instead.
"""
# 长度
n = len(nums)
# 记录图中i-1的位置
pos = n - 1
for i in range(n-1, 0, -1):
# 如果降序破坏，说明找到了i
if nums[i] > nums[i-1]:
pos = i-1
break

for i in range(n-1, pos, -1):
# 从最后开始找大于pos位置的
if nums[i] > nums[pos]:
# 先交换元素，在进行翻转
nums[i], nums[pos] = nums[pos], nums[i]
# 翻转[pos+1, n]区间
nums[pos+1:] = nums[n:pos:-1]
return False
return True

def permute(self, nums: List[int]) -> List[List[int]]:
ret = []
# 从小到大排序，获得最小排列
nums = sorted(nums)
ret.append(nums.copy())
# 如果还有下一个排列则继续调用
while not self.get_next(nums):
# 要.copy()是因为Python中存储的引用，如果不加copy
# 会导致当nums发生变化之后，ret中存储的数据也会变化
ret.append(nums.copy())
return ret
{"ft_lang_label":"__label__zh","ft_lang_prob":0.9548152,"math_prob":0.9890802,"size":3066,"snap":"2021-04-2021-17","text_gpt3_token_len":2241,"char_repetition_ratio":0.08719791,"word_repetition_ratio":0.044247787,"special_character_ratio":0.2159165,"punctuation_ratio":0.14051522,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9910576,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-01-18T22:29:26Z\",\"WARC-Record-ID\":\"<urn:uuid:23b69906-7eaa-4ad5-8751-75d59d70590d>\",\"Content-Length\":\"53992\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e6afba0b-205a-402e-a37b-fdd0cfe0a474>\",\"WARC-Concurrent-To\":\"<urn:uuid:37ba448b-331b-41bf-9de6-8214e9faf83b>\",\"WARC-IP-Address\":\"59.110.85.65\",\"WARC-Target-URI\":\"https://www.go2live.cn/nocate/leetcode46-%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E6%B1%82%E5%85%A8%E6%8E%92%E5%88%97%EF%BC%8C%E8%BF%99%E6%AC%A1%E6%98%AF%E7%9C%9F%E5%85%A8%E6%8E%92%E5%88%97.html\",\"WARC-Payload-Digest\":\"sha1:2C4T4DO7THINLE4IS2PWTDGVSHBOQWJP\",\"WARC-Block-Digest\":\"sha1:AMRKVCWD635H2RWI6HLEMYZOCM4H3QR2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-04/CC-MAIN-2021-04_segments_1610703517159.7_warc_CC-MAIN-20210118220236-20210119010236-00648.warc.gz\"}"}