daily leetcode - combination-sum-ii - !
题目地址
https://leetcode.com/problems/combination-sum-ii/
题目描述
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]
]
思路
这道题跟之前那道 Combination Sum 本质没有区别,只需要改动一点点即可,之前那道题给定数组中的数字可以重复使用,而这道题不能重复使用,只需要在之前的基础上修改两个地方即可,首先在递归的 for 循环里加上 if (i > start && num[i] == num[i - 1]) continue; 这样可以防止 res 中出现重复项,然后就在递归调用 helper 里面的参数换成 i+1,这样就不会重复使用数组中的数字了,代码如下:
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& num, int target) {
vector<vector<int>> res;
vector<int> out;
sort(num.begin(), num.end());
helper(num, target, 0, out, res);
return res;
}
void helper(vector<int>& num, int target, int start, vector<int>& out, vector<vector<int>>& res) {
if (target < 0) return;
if (target == 0) { res.push_back(out); return; }
for (int i = start; i < num.size(); ++i) {
if (i > start && num[i] == num[i - 1]) continue;
out.push_back(num[i]);
helper(num, target - num[i], i + 1, out, res);
out.pop_back();
}
}
};
思路 2
这道题目是求集合,并不是求极值
,因此动态规划不是特别切合,因此我们需要考虑别的方法。
这种题目其实有一个通用的解法,就是回溯法。
网上也有大神给出了这种回溯法解题的
通用写法,这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路,我画了一张图:
通用写法的具体代码见下方代码区。
关键点解析
- 回溯法
- 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()
本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode