"""
子集（元素无重不可复选）
78
组合（元素无重不可复选）
77
排列（元素无重不可复选）
46
子集/组合（元素可重不可复选）
90
排列（元素可重不可复选）
47
子集/组合（元素无重可复选）
39
"""
# 形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，backtrack 核心代码如下：
track = []
used = []


def backtrack(nums, start: int):
    # 回溯算法标准框架
    for i in range(start, len(nums)):
        # 做选择
        track.append(nums[i])
        # 注意参数
        backtrack(nums, i + 1)
        # 撤销选择
        track.pop()


def backtrack(nums):
    for i in range(len(nums)):
        # 剪枝逻辑
        if used[i]:
            continue
        # 做选择
        used[i] = True
        track.append(nums[i])

        backtrack(nums)
        # 撤销选择
        track.pop()
        used[i] = False


# 形式二、元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝，backtrack 核心代码如下：

nums = [2,3,6,7]
target = 7
nums.sort()


# 组合/子集问题回溯算法框架
def backtrack(nums, start: int):
    # 回溯算法标准框架
    for i in range(start, len(nums)):
        # 剪枝逻辑，跳过值相同的相邻树枝
        if i > start and nums[i] == nums[i - 1]:
            continue
        # 做选择
        track.append(nums[i])
        # 注意参数
        backtrack(nums, i + 1)
        # 撤销选择
        track.pop()

nums.sort()


# 排列问题回溯算法框架
def backtrack(nums):
    for i in range(len(nums)):
        # 剪枝逻辑
        if used[i]:
            continue
        # 剪枝逻辑，固定相同的元素在排列中的相对位置
        if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
            continue
        # 做选择
        used[i] = True
        track.append(nums[i])

        backtrack(nums)
        # 撤销选择
        track.pop()
        used[i] = False


# 形式三、元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可，backtrack 核心代码如下:
# 组合/子集问题回溯算法框架
def backtrack(nums, start: int):
    # 回溯算法标准框架
    for i in range(start, len(nums)):
        # 做选择
        track.append(nums[i])
        # 注意参数
        backtrack(nums, i)
        # 撤销选择
        track.pop()


# 排列问题回溯算法框架
def backtrack(nums):
    for i in range(len(nums)):
        # 做选择
        track.append(nums[i])
        backtrack(nums)
        # 撤销选择
        track.pop()