LeetCode-39. 组合总和
2020-09-092020-09-18
问题地址
LeetCode39. 组合总和
问题描述
规则
- 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
- candidates 中的数字可以无限制重复被选取。
说明
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
示例
- 示例一：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
- 示例二：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
提示
- $1 <= candidates.length <= 30$
- $1 <= candidates[i] <= 200$
- candidate 中的每个元素都是独一无二的。
- $1 <= target <= 500$
解析
解题思路
- 今天的题目和前两天的每日一题类似，都可可以尝试用「搜索回溯」的方法来解决。直接看官方解法。
- 相似题目：
数据操作分析
复杂度分析
- 时间复杂度
- 空间复杂度
编码实现
官方解法
方法一：搜索回溯
思路：
- 对于这类寻找所有可行解的题，我们都可以尝试用「搜索回溯」的方法来解决。
- 回到本题，我们定义递归函数 dfs(target, combine, idx) 表示当前在 candidates 数组的第 idx 位，还剩 target 要组合，已经组合的列表为 combine。递归的终止条件为 target = 0$ 进行剪枝，所以实际运行情况是远远小于这个上界的。
- 空间复杂度：O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(\textit{target}) 层。
编码实现
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> combine = new ArrayList<Integer>();
dfs(candidates, target, ans, combine, 0);
return ans;
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
if (idx == candidates.length) {
return;
}
if (target == 0) {
ans.add(new ArrayList<Integer>(combine));
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.add(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.remove(combine.size() - 1);
}
}
}
精彩评论
跳转地址1：回溯算法 + 剪枝（回溯经典例题详解）
思路
- 根据示例 1：输入: candidates = [2, 3, 6, 7]，target = 7。
- 候选数组里有 2，如果找到了组合总和为 7 – 2 = 5 的所有组合，再在之前加上 2 ，就是 7 的所有组合；
- 同理考虑 3，如果找到了组合总和为 7 – 3 = 4 的所有组合，再在之前加上 3 ，就是 7 的所有组合，依次这样找下去。
- 基于以上的想法，可以画出如下的树形图。建议大家自己在纸上画出这棵树，这一类问题都需要先画出树形图，然后编码实现。
- 编码通过 深度优先遍历 实现，使用一个列表，在 深度优先遍历 变化的过程中，遍历所有可能的列表并判断当前列表是否符合题目的要求，成为「回溯算法」（个人理解，非形式化定义）。
- 回溯算法的总结我写在了「力扣」第 46 题（全排列）的题解 《回溯算法入门级详解 + 经典例题列表（持续更新）》 中，如有需要请前往观看。
画出树形图
- 2020 年 9 月 9 日补充：以下给出的是一种树形图的画法。对于组合来说，还可以根据一个数选和不选画树形图，请参考 官方题解 或者 @elegant-pike 的 评论。
- 以输入：candidates = [2, 3, 6, 7], target = 7 为例：
说明
- 以 target = 7 为 根结点 ，创建一个分支的时 做减法 ；
- 每一个箭头表示：从父亲结点的数值减去边上的数值，得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值；
- 减到 00 或者负数的时候停止，即：结点 00 和负数结点成为叶子结点；
- 所有从根结点到结点 00 的路径（只能从上往下，没有回路）就是题目要找的一个结果。
-
这棵树有 44 个叶子结点的值 00，对应的路径列表是 [[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]，而示例中给出的输出只有 [[7], [2, 2, 3]]。即：题目中要求每一个符合要求的解是 不计算顺序 的。下面我们分析为什么会产生重复。
针对具体例子分析重复路径产生的原因（难点）
- 产生重复的原因是：在每一个结点，做减法，展开分支的时候，由于题目中说 每一个元素可以重复使用，我们考虑了 所有的 候选数，因此出现了重复的列表。
- 一种简单的去重方案是借助哈希表的天然去重的功能，但实际操作一下，就会发现并没有那么容易。
- 可不可以在搜索的时候就去重呢？答案是可以的。遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要 按某种顺序搜索。具体的做法是：每一次搜索的时候设置 下一轮搜索的起点 begin，请看下图。
- 即：从每一层的第 22 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。
- 友情提示：如果题目要求，结果集不计算顺序，此时需要按顺序搜索，才能做到不重不漏。「力扣」第 47 题（ 全排列 II ）、「力扣」第 15 题（ 三数之和 ）也使用了类似的思想，使得结果集没有重复。
复杂度分析
- 这个问题的复杂度分析是在我的能力之外的，这里给出我的思考。
- 我的结论是：时间复杂度与 candidate 数组的值有关：
- 如果 candidate 数组的值都很大，target 的值很小，那么树上的结点就比较少；
- 如果 candidate 数组的值都很小，target 的值很大，那么树上的结点就比较多。
- 所以时间复杂度与空间复杂度不确定。
补充
- 参考代码 1 和参考代码 2 的 Python 部分，没有严格按照回溯算法来写，这里需要了解的知识点是：
- Python3 的 [1, 2] + [3] 语法生成了新的列表，一层一层传到根结点以后，直接 res.append(path) 就可以了；
- 基本类型变量在传参的时候，是复制，因此变量值的变化在参数里体现就行，所以 Python3 的代码看起来没有「回溯」这个步骤。
编码实现
参考代码一
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, 0, len, target, path, res);
return res;
}
/**
* @param candidates 候选数组
* @param begin 搜索起点
* @param len 冗余变量，是 candidates 里的属性，可以不传
* @param target 每减去一个元素，目标值变小
* @param path 从根结点到叶子结点的路径，是一个栈
* @param res 结果集列表
*/
private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
// target 为负数和 0 的时候不再产生新的孩子结点
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
// 重点理解这里从 begin 开始搜索的语意
for (int i = begin; i < len; i++) {
path.addLast(candidates[i]);
// 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
dfs(candidates, i, len, target - candidates[i], path, res);
// 状态重置
path.removeLast();
}
}
}
参考代码二：增加控制台输出
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (k <= 0 || n < k) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(n, k, 1, path, res);
return res;
}
private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i <= n; i++) {
path.addLast(i);
System.out.println("递归之前 => " + path);
dfs(n, k, i + 1, path, res);
path.removeLast();
System.out.println("递归之后 => " + path);
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 5;
int k = 3;
List<List<Integer>> res = solution.combine(n, k);
System.out.println(res);
}
}
优化：剪枝提速
思路
- 根据上面画树形图的经验，如果 target 减去一个数得到负数，那么减去一个更大的树依然是负数，同样搜索不到结果。基于这个想法，我们可以对输入数组进行排序，添加相关逻辑达到进一步剪枝的目的；
- 排序是为了提高搜索速度，对于解决这个问题来说非必要。但是搜索问题一般复杂度较高，能剪枝就尽量剪枝。实际工作中如果遇到两种方案拿捏不准的情况，都试一下。
复杂度分析
- 时间复杂度：。
- 空间复杂度：。
编码实现
参考代码三：
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
// 排序是剪枝的前提
Arrays.sort(candidates);
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, 0, len, target, path, res);
return res;
}
private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
// 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
// 重点理解这里剪枝，前提是候选数组已经有序，
if (target - candidates[i] < 0) {
break;
}
path.addLast(candidates[i]);
dfs(candidates, i, len, target - candidates[i], path, res);
path.removeLast();
}
}
}
总结
什么时候使用 used 数组，什么时候使用 begin 变量
- 有些朋友可能会疑惑什么时候使用 used 数组，什么时候使用 begin 变量。这里为大家简单总结一下：
- 排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
- 组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。
- 注意：具体问题应该具体分析， 理解算法的设计思想 是至关重要的，请不要死记硬背。
补充说明
- 如果对于「回溯算法」的理解还很模糊的朋友，建议在「递归」之前和「递归」之后，把 path 变量的值打印出来看一下，以加深对于程序执行流程的理解。
-
针对参考代码 1 添加打印输出：
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, 0, len, target, path, res);
return res;
}
private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
path.addLast(candidates[i]);
System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));
dfs(candidates, i, len, target - candidates[i], path, res);
path.removeLast();
System.out.println("递归之后 => " + path);
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] candidates = new int[]{2, 3, 6, 7};
int target = 7;
List<List<Integer>> res = solution.combinationSum(candidates, target);
System.out.println("输出 => " + res);
}
}
- 针对参考代码 2 添加打印输出：
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Arrays.sort(candidates);
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, 0, len, target, path, res);
return res;
}
private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
if (target - candidates[i] < 0) {
break;
}
path.addLast(candidates[i]);
System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));
dfs(candidates, i, len, target - candidates[i], path, res);
path.removeLast();
System.out.println("递归之后 => " + path);
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] candidates = new int[]{2, 3, 6, 7};
int target = 7;
List<List<Integer>> res = solution.combinationSum(candidates, target);
System.out.println("输出 => " + res);
}
}
跳转地址2：超强gif助你理解使用“动态规划”求解本题
前言
思路
- 对于目标值target，它一定是由比它小的数相加得到的。比如5=1+4=2+3，而4=3+1=2+2，3=2+1，2=1+1…， 也就是说，从1开始，我们依次求解每个数可以有几种形成的方式，则数值更高的数的组合方式建立在数值低的数的组合方式上得到，好吧我自己都没看懂我说的话，直接看图片吧。
准备工作
- 初始化一个数组dict，键是1~target，值初始化为空列表。
分析组成方式
- 得到：1只可以由[1]这1种方式组成。
- 得到：2只可以由[1,1],[2]这2种方式组成。
- 得到：3可以由[1,1,1],[1,2],[3]这3种方式组成。
- 得到：4可以由[1,1,1,1],[1,1,2],[2,2],[3,1],[4]这5种方式组成。
- 得到：5可以由[1,1,1,1,1],[1,1,1,2],[2,2,1],[3,1,1],[3,2],[4,1]这6种方式组成。
总结
- 求解一个值，需要求解上一个值，进而需要求解上上个值…，这种方法就是动态规划。重复的值只需要进行一次，而后再使用到这个值时，只需要将他的结果拿来适当增加即可。
感谢
- 受编程水平限制，博主最初只提供了Python3的代码，欢迎其他编程语言爱好者提供相应代码复现动态规划。
- C++版本1算法由@lan-yun-2提供。
- C++版本2算法由@pris_bupt提供。
- Java算法由@liu-li-8提供。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
dict = {}
for i in range(1,target+1):
dict[i]=[]
for i in range(1,target+1):
for j in candidates:
if i==j:
dict[i].append([i])
elif i>j:
for k in dict[i-j]:
x = k[:]
x.append(j)
x.sort() # 升序，便于后续去重
if x not in dict[i]:
dict[i].append(x)
return dict[target]
// 由@lan-yun-2提供
map<int, set<vector<int> > > dpkv;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
set<vector<int> > avectorset;
// 初始化
for(int i = 1; i <= target; i++){
dpkv[i] = avectorset; // 都赋值成一个空的数组
}
// 开始递推
for(int j = 1; j <= target; j++){
for(vector<int>::iterator it = candidates.begin(); it != candidates.end(); it++){
if(j == *it){
// 直接作为一个vector<int>加入
vector<int> v_only_one_num;
v_only_one_num.push_back(j);
dpkv[j].insert(v_only_one_num);
} else if(j > *it){ // 用dp[j - *it] 作为结果
// 遍历dp[j - *it]
for(set<vector<int> >::iterator its = dpkv[j - *it].begin(); its != dpkv[j - *it].end(); its++){
vector<int> the_vector = (*its);
the_vector.push_back(*it);
sort(the_vector.begin(), the_vector.end());
dpkv[j].insert(the_vector);
}
}
}
}
// 将set加工成vector
vector<vector<int>> target_v;
for(set<vector<int> >::iterator its = dpkv[target].begin(); its != dpkv[target].end(); its++){
target_v.push_back(*its);
}
return target_v;
}
};
// 由@pris_bupt提供
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
unordered_map<int, set<vector<int>>>dict;
for (int i = 1; i <= target; i++)
for (int it : candidates)
if (i == it) dict[i].insert(vector<int>{it});
else if (i > it)
for (auto ivec : dict[i - it]) {
ivec.push_back(it);
sort(ivec.begin(), ivec.end());
if(dict[i].count(ivec)==0)
dict[i].insert(ivec);
}
vector<vector<int>>ans;
for (auto it : dict[target]) ans.push_back(it);
return ans;
}
// 由@liu-li-8提供
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Map<Integer,Set<List<Integer>>> map = new HashMap<>();
//对candidates数组进行排序
Arrays.sort(candidates);
int len = candidates.length;
for(int i = 1;i <= target;i++){
//初始化map
map.put(i,new HashSet<>());
//对candidates数组进行循环
for(int j = 0;j < len&&candidates[j] <= target;j++){
if(i == candidates[j]){
//相等即为相减为0的情况，直接加入set集合即可
List<Integer> temp = new ArrayList<>();
temp.add(i);
map.get(i).add(temp);
}else if(i > candidates[j]){
//i-candidates[j]是map的key
int key = i-candidates[j];
//使用迭代器对对应key的set集合进行遍历
//如果candidates数组不包含这个key值，对应的set集合会为空，故这里不需要做单独判断
for(Iterator iterator = map.get(key).iterator();iterator.hasNext();){
List list = (List) iterator.next();
//set集合里面的每一个list都要加入candidates[j]，然后放入到以i为key的集合中
List tempList = new ArrayList<>();
tempList.addAll(list);
tempList.add(candidates[j]);
//排序是为了通过set集合去重
Collections.sort(tempList);
map.get(i).add(tempList);
}
}
}
}
result.addAll(map.get(target));
return result;
}
}