previous permutation lintcode51

TLE版本

这个版本无法通过。只是为了自己加深dfs的理解。
时间复杂度O(N^N)， 对于每一个位置，都要遍历n次， 有n个位置。

from typing import (
    List,
)

class Solution:
    """
    @param nums: A list of integers
    @return: A list of integers that's previous permuation
    """
    def dfs(self, nums, query, sub_ans, per_lst, visited):
        if query == sub_ans:
            return True
        if len(sub_ans) == len(nums):
            per_lst.append(sub_ans[:])
            # print(per_lst)
            return False
        for i in range(len(nums)):
            if i not in visited:
                sub_ans.append(nums[i])
                visited.append(i)
                if self.dfs(nums, query, sub_ans, per_lst, visited):
                    # print(per_lst)
                    if not per_lst:
                        return nums[::-1]
                    return per_lst[-1]
                sub_ans.pop()
                visited.pop()
        
    def previous_permuation(self, nums: List[int]) -> List[int]:
        # write your code here
        query = nums.copy()
        nums = sorted(nums)
        return self.dfs(nums, query, [], [], [])