标题要求
给你一个 无重复元素 的整数数组 candidates 和一个目的整数 target ,找出 candidates 中可以使数字和为目的数 target 的 全部 差别组合 ,并以列心情势返回。你可以按 恣意次序 返回这些组合。
candidates 中的 同一个 数字可以 无穷制重复被选取 。假如至少一个数字的被选数目差别,则两种组合是差别的。
对于给定的输入,包管和为 target 的差别组合数少于 150 个。
示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
表明:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。留意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。
示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:
输入: candidates = [2], target = 1
输出: []
解题思绪
这道题是比力范例的回溯算法的标题,必要留意的是怎样克制重复效果。
因为标题中说到,candidates数组中无重复元素,以是可以直接通过只选择index及其之后的元素,来克制重复。
假如标题中给的candidates数组有重复元素,则必要判断当前index与之前的元素是否有重复,有重复的元素都必要过滤。
Java代码 |