class Solution(object):
    # 回溯法:当前字符若是数字则直接搜索下一个位置，若当前是英文字母，则分成两种情况分别向下搜索。
    # 当当前下标与字符串长度相等则将变量串添加到结果集合中。
    def letterCasePermutation(self, S):
        """
        :type S: str
        :rtype: List[str]
        """
        res = []
        self.helper("", S, res, 0)
        return res

    def helper(self, pre, S, res, index):
        if index == len(S):
            res.append(pre)
        else:
            ch = S[index]
            if str.isdigit(ch):
                self.helper(pre+ch, S, res, index+1)
            else:
                ch = str.lower(ch)
                self.helper(pre+ch, S, res, index+1)
                ch = str.upper(ch)
                self.helper(pre+ch, S, res, index+1)

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        # 采用前后元素交换的办法，dfs解题
        # 就是第一个数分别以后面的数进行交换
        self.dfs(nums, 0, res)
        return res

    def dfs(self, nums, begin, res):
        if begin == len(nums):
            res.append(nums[:])
            return
        else:
            # 第i个数分别与它后面的数字交换就能得到新的排列
            for i in range(begin, len(nums)):
                self.swap(nums, begin, i)
                self.dfs(nums, begin+1, res)
                # 将前面的调换恢复回去
                self.swap(nums, begin, i)

    def swap(self, nums, i, j):
        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp

s = Solution()
nums = [1,3,4]
r = s.permute(nums)
print(r)

输出：
[[1, 3, 4], [1, 4, 3], [3, 1, 4], [3, 4, 1], [4, 3, 1], [4, 1, 3]]

class Solution:
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # 从后往前找到序列中第一个非递增的数的索引
        i = len(nums) - 2
        while i >= 0:
            if nums[i] < nums[i+1]:
                break
            i -= 1
        if i < 0:
            nums.sort()
            return
        # 从后往前找到后面序列中第一个比nums[i]大的数
        j = len(nums) - 1
        while j > i:
            if nums[j] > nums[i]:
                break
            j -= 1
        # 交换位置
        self.swap(nums, i, j)
        # 将i后面的序列逆序
        nums[i+1:] = nums[i+1:][::-1]

    def swap(self, nums, i, j):
        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp

s = Solution()
nums = [1,2]
r = s.nextPermutation(nums)
print(nums)

输出：
[2, 1]

class Solution:
    # 每一轮搜索选择一个数加入列表中，同时我们还要维护一个全局的布尔数组，
    # 来标记哪些元素已经被加入列表了，这样在下一轮搜索中要跳过这些元素。
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 新建一个used数组，大小与nums相同，用来标记在本次DFS读取中，位置i的元素是否已经被添加到list中了。
        used = [False for i in range(len(nums))]
        res = []
        tmp = []  # 临时数组用于存放每一轮搜索访问到的元素
        self.helper(nums, tmp, res, used)
        return res

    def helper(self, nums, tmp, res, used):
        if len(tmp) == len(nums):
            res.append(tmp[:])
        else:
            i = 0
            while i < len(nums):
                # 遇到已经加过的元素就跳过
                if used[i]:
                    i += 1
                    continue
                # 加入该元素后继续搜索
                used[i] = True
                tmp.append(nums[i])
                self.helper(nums, tmp, res, used)
                tmp.pop(-1)
                used[i] = False
                i += 1

class Solution:
    # 每一轮搜索选择一个数加入列表中，同时我们还要维护一个全局的布尔数组，
    # 来标记哪些元素已经被加入列表了，这样在下一轮搜索中要跳过这些元素。
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 先对数组排序，使得大小相同的元素排在一起。
        nums.sort()
        # 新建一个used数组，大小与nums相同，用来标记在本次DFS读取中，位置i的元素是否已经被添加到list中了。
        used = [False for i in range(len(nums))]
        res = []
        tmp = []  # 临时数组用于存放每一轮搜索访问到的元素
        self.helper(nums, tmp, res, used)
        return res

    def helper(self, nums, tmp, res, used):
        if len(tmp) == len(nums):
            res.append(tmp[:])
        else:
            i = 0
            while i < len(nums):
                # 遇到已经加过的元素就跳过
                if used[i]:
                    i += 1
                    continue
                # 加入该元素后继续搜索
                used[i] = True
                tmp.append(nums[i])
                self.helper(nums, tmp, res, used)
                tmp.pop(-1)
                used[i] = False
                # 跳过本轮的重复元素，确保每一轮只会加唯一的数字
                while i < len(nums)-1 and nums[i] == nums[i+1]:
                    i += 1
                i += 1