Leetcode 39. 组合总和

程序员 · 2024-9-4 10:02:27

标题要求

给你一个无重复元素的整数数组 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代码

Leetcode 39. 组合总和

所属分类: 问答交流

新帖推荐: 30日

推荐作品