题目地址
https://leetcode.com/problems/combination-sum-ii/description/
题目描述
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
思路
这道题目是求集合,并不是求极值
,因此动态规划不是特别切合,因此我们需要考虑别的方法。
这种题目其实有一个通用的解法,就是回溯法。
网上也有大神给出了这种回溯法解题的
通用写法,这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路,我画了一张图:
通用写法的具体代码见下方代码区。
关键点解析
- 回溯法
- backtrack 解题公式
代码
- 语言支持: Javascript,Python3
/* * @lc app=leetcode id=40 lang=javascript * * [40] Combination Sum II * * https://leetcode.com/problems/combination-sum-ii/description/ * * algorithms * Medium (40.31%) * Total Accepted: 212.8K * Total Submissions: 519K * Testcase Example: '[10,1,2,7,6,1,5]\n8' * * Given a collection of candidate numbers (candidates) and a target number * (target), find all unique combinations in candidates where the candidate * numbers sums to target. * * Each number in candidates may only be used once in the combination. * * Note: * * * All numbers (including target) will be positive integers. * The solution set must not contain duplicate combinations. * * * Example 1: * * * Input: candidates = [10,1,2,7,6,1,5], target = 8, * A solution set is: * [ * [1, 7], * [1, 2, 5], * [2, 6], * [1, 1, 6] * ] * * * Example 2: * * * Input: candidates = [2,5,2,1,2], target = 5, * A solution set is: * [ * [1,2,2], * [5] * ] * * */ function backtrack(list, tempList, nums, remain, start) { if (remain < 0) return; else if (remain === 0) return list.push([...tempList]); for (let i = start; i < nums.length; i++) { // 和39.combination-sum 的其中一个区别就是这道题candidates可能有重复 // 代码表示就是下面这一行 if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates tempList.push(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i + 1); // i + 1代表不可以重复利用, i 代表数字可以重复使用 tempList.pop(); } } /** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum2 = function(candidates, target) { const list = []; backtrack(list, [], candidates.sort((a, b) => a - b), target, 0); return list; };
Python3 Code:
class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: """ 与39题的区别是不能重用元素,而元素可能有重复; 不能重用好解决,回溯的index往下一个就行; 元素可能有重复,就让结果的去重麻烦一些; """ size = len(candidates) if size == 0: return [] # 还是先排序,主要是方便去重 candidates.sort() path = [] res = [] self._find_path(candidates, path, res, target, 0, size) return res def _find_path(self, candidates, path, res, target, begin, size): if target == 0: res.append(path.copy()) else: for i in range(begin, size): left_num = target - candidates[i] if left_num < 0: break # 如果存在重复的元素,前一个元素已经遍历了后一个元素与之后元素组合的所有可能 if i > begin and candidates[i] == candidates[i-1]: continue path.append(candidates[i]) # 开始的 index 往后移了一格 self._find_path(candidates, path, res, left_num, i+1, size) path.pop()
相关题目
- 39.combination-sum
- 46.permutations
- 47.permutations-ii
- 78.subsets
- 90.subsets-ii
- 113.path-sum-ii
- 131.palindrome-partitioning
题目地址 https://leetcode.com/problems/combination-sum/description/ 题目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all uniqu…
LeetCode题解113.path-sum-ii题目地址 https://leetcode.com/problems/path-sum-ii/description/ 题目描述 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. Note: A leaf…
LeetCode题解45.跳跃游戏 II给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数…
LeetCode题解140. 单词拆分 II批注: 由于"可以重复使用字典中的单词", 因此稍微难一点定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明:分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1:输入:s = "catsanddog"wordDict = […
LeetCode题解126. 单词接龙 II (Hard)给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。说明:如果不存在这样的转换序列,返回一个空列表。所有单词具有相同的长度。所有单词只由小写字母组成。字典中不存在重复的单词。…