（3）回溯算法团灭子集、组合、排列问题 -- 元素无重可复选-Toy模板网

这篇具有很好参考价值的文章主要介绍了（3）回溯算法团灭子集、组合、排列问题 -- 元素无重可复选。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

回溯算法团灭子集、组合、排列问题
根据元素是否重复和是否可复选，分为以下三种变体：
1、元素无重不可复选
2、元素有重不可复选
3、元素无重可复选

该篇给出第三种情况的代码，另外两种的实现见上方变体链接。文章来源地址https://www.toymoban.com/news/detail-698079.html


class NoRepeatAndMultiple:
    """
    元素无重可复选
    """
    def subsets(self, nums: List[int], target) -> List[List[int]]:
        """
        相当于目标和问题
        :param nums:
        :param target:
        :return:
        """
        self.res = []
        self.track = []
        self.track_sum = 0
        self.s_backtrack(nums, 0, target)
        return self.res

    def s_backtrack(self, nums, start, target):
        #  base case
        if self.track_sum == target:
            self.res.append(self.track[:])
            return

        # base case
        if self.track_sum > target:
            return

        for i in range(start, len(nums)):
            # 做选择
            self.track_sum += nums[i]
            self.track.append(nums[i])

            # 通过 start 参数控制树枝的遍历，避免产⽣重复的⼦集
            self.s_backtrack(nums, i, target)

            # 撤销选择
            self.track_sum -= nums[i]
            self.track.pop()

    def combination(self, nums: List[int], k: int) -> List[List[int]]:
        """
        组合问题，这里等价于子集问题
        :param nums:
        :param k:
        :return:
        """
        pass

    def permute(self, nums: List[int]) -> List[List[int]]:
        """
        排列问题
        :param nums:
        :return:
        """
        self.res = []
        self.track = []
        self.p_backtrack(nums)
        return self.res

    def p_backtrack(self, nums):
        #  base case
        if len(self.track) == len(nums):
            self.res.append(self.track[:])
            return

        for i in range(0, len(nums)):

            # 做选择
            self.track.append(nums[i])

            # 通过 start 参数控制树枝的遍历，避免产⽣重复的⼦集
            self.p_backtrack(nums)

            # 撤销选择
            self.track.pop()