46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        def backtracing(nums):
            # 终止条件：当路径上的元素数量等于最大值
            if len(path) == len(nums):
                res.append(path[:])
                return

            for i in range(len(nums)):
                if nums[i] not in path:
                    path.append(nums[i])
                    # 递归搜索
                    backtracing(nums)
                    # 撤销选择
                    path.pop()
        backtracing(nums)
        return res

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

# 对于数组中包含重复数字，需要对重复的数字提前进行标注，在访问时及时去重
class Solution:
    res = []
    path = []
    # 回溯算法
    def backtracing(self, nums: List[int], visited: List[bool]):
        # 递归的终止条件
        if len(nums) == len(self.path):
            self.res.append(self.path[:])
            return 

        for i in range(len(nums)):
            # 需要及时去重，如果相同元素之前访问过，则跳过
            if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:
                continue
            # 元素没有访问过
            if not visited[i]:
                # 访问之后需要进行标记
                visited[i] = True
                self.path.append(nums[i])
                self.backtracing(nums, visited)
                self.path.pop()
                # 回溯之后对元素进行恢复
                visited[i] = False

    # 主函数
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 清除缓存
        self.res.clear()
        self.path.clear()
        # 需要对nums进行排序
        nums.sort()
        # 用于记录是否访问过相同元素
        visited = [False]*len(nums)
        self.backtracing(nums, visited)
        return self.res

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

class Solution:
    def backtrace(self, nums, index, res, path):
        # 空数组
        res.append(path[:])
        # 从第0个位置开始，进行深度优先搜索
        for i in range(index, len(nums)):
            if i > index and nums[i] == nums[i-1]:
                continue
            path.append(nums[i])
            self.backtrace(nums, i+1, res, path)
            path.pop()


    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # 首先对数组排序
        nums.sort()
        res, path = [], []
        self.backtrace(nums, 0, res, path)
        return res

784. 字母大小写全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

# 大小写转换
class Solution:
    def dfs(self, s, i, path, ans):
        # 终止条件
        if i == len(s):
            ans.append(path[:])
            return 

        self.dfs(s, i+1, path+s[i], ans)
        # 当字符为小写字母，转换为大写并添加
        if ord('a') <= ord(s[i]) <= ord('z'):
            self.dfs(s, i+1, path + s[i].upper(), ans)
        # 当字符为大写字母是，转换为小写并添加
        elif ord('A') <= ord(s[i]) <= ord('Z'):
            self.dfs(s, i+1, path + s[i].lower(), ans)

    def letterCasePermutation(self, s: str) -> List[str]:
        ans, path = [], ''
        self.dfs(s, 0, path, ans)
        return ans

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

class Solution:
    path = []
    res = []
    def backtracing(self, candidates: List[int], target:int, sum_all:int, start_index:int):
        # 递归的终止条件
        if sum_all > target:
            return
        if sum_all == target:
            self.res.append(self.path[:])
            return 
        
        # 开始遍历查找
        for i in range(start_index, len(candidates)):
            # 循环终止条件
            if sum_all + candidates[i] > target:
                break

            sum_all += candidates[i]
            self.path.append(candidates[i])
            # 回溯
            self.backtracing(candidates, target, sum_all, i)
            sum_all -= candidates[i]
            self.path.pop()

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.path.clear()
        self.res.clear()
        candidates.sort()
        self.backtracing(candidates, target, 0, 0)
        # print(self.res)
        return self.res

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

# 本题主要考虑去重
class Solution:
    res = []
    path = []
    def backtracing(self, candidates: List[int], target: int, sum_all: int, start_index: int):
        # 递归的终止条件
        if sum_all > target:
            return 
        if sum_all == target:
            self.res.append(self.path[:])
            return
        # 进行回溯
        for i in range(start_index, len(candidates)):
            # 终止条件
            if sum_all + candidates[i] > target:
                break
            # 去重操作
            if i > start_index and candidates[i] == candidates[i-1]:
                continue

            sum_all += candidates[i]
            self.path.append(candidates[i])
            self.backtracing(candidates, target, sum_all, i+1)
            sum_all -= candidates[i]
            self.path.pop()

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res.clear()
        self.path.clear()
        # 先进行排序
        candidates.sort()
        self.backtracing(candidates, target, 0, 0)
        return self.res