题目:
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
思路:使用递归的思想,回溯和减枝
程序:
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() length = len(candidates) if length <= 0: return result = [] temp_result = [] def auxiliary(index, temp_result, target): if target == 0: result.append(temp_result) return if index == length or target < candidates[index]: return auxiliary(index, temp_result + [candidates[index]], target - candidates[index]) auxiliary(index + 1, temp_result, target) auxiliary(0, temp_result, target) return result