Leetcode 39. 组合总和

程序员 2024-9-4 10:02:27 101 0 来自 中国
标题要求

给你一个 无重复元素 的整数数组 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代码
您需要登录后才可以回帖 登录 | 立即注册

Powered by CangBaoKu v1.0 小黑屋藏宝库It社区( 冀ICP备14008649号 )

GMT+8, 2024-12-4 16:39, Processed in 0.172490 second(s), 32 queries.© 2003-2025 cbk Team.

快速回复 返回顶部 返回列表