题解 | #牛群分组II#

• 题目考察的知识点 : 回溯
• 题目解答方法的文字分析：

1. 用回溯法枚举给定数组的所有可能组合。具体来说，对于每个数，可以选择不选它或选它一次……直到不能再选为止。在搜索过程中，每当组合的元素之和等于目标值时，就将该组合加入答案中。
2. 为了避免重复，每次从当前位置开始向后搜索，而不是从头开始搜索。同时，由于题目要求按升序排序返回结果，因此在搜索之前先对数组进行排序。
3. 在搜索的过程中，需要考虑去重。由于 candidates 数组中的数字可以重复使用，所以需要确保同一层级中不能有相同的数字被选择。如果多个相同的数字都能够满足条件，只需选择其中一个即可，因此可以跳过后面的相同数字，避免重复

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param candidates int整型一维数组
# @param target int整型
# @return int整型二维数组
#
class Solution:
    def cowCombinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []

        candidates.sort()

        def backtrack(start: int, target: int) -> None:
            if target == 0:
                res.append(path[:])
                return

            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                if candidates[i] > target:
                    break
                path.append(candidates[i])
                backtrack(i + 1, target - candidates[i])
                path.pop()

        backtrack(0, target)

        return res