首页 > 极客资料 博客日记

LeetCode40.组合总和II

2024-08-14 21:30:03极客资料围观24

本篇文章分享LeetCode40.组合总和II,对你有帮助的话记得收藏一下,看极客之家收获更多编程知识

LeetCode40.组合总和II

力扣题目链接(opens new window)

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明: 所有数字(包括目标数)都是正整数。解集不能包含重复的组合。

  • 示例 1:
  • 输入: candidates = [10,1,2,7,6,1,5], target = 8,
  • 所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
  • 示例 2:
  • 输入: candidates = [2,5,2,1,2], target = 5,
  • 所求解集为:
[
  [1,2,2],
  [5]
]

思路

这道题目和[LeetCode39. 组合总和 - Tomorrowland_D - 博客园 (cnblogs.com)]()如下区别:

  1. 本题candidates 中的每个数字在每个组合中只能使用一次。
  2. 本题数组candidates的元素是有重复的,而[LeetCode39. 组合总和 - Tomorrowland_D - 博客园 (cnblogs.com)]()是无重复元素的数组candidates

最后本题和[LeetCode39. 组合总和 - Tomorrowland_D - 博客园 (cnblogs.com)]()要求一样,但是解集不能包含重复的组合。

本题的难点在于区别2中:集合(数组candidates)有重复元素,但还不能有重复的组合

  • 我们直观的可以想到以下办法:我把所有组合求出来,再用set或者map去重,这么做很容易超时!

  • 所以要在搜索的过程中就去掉重复组合。

  • 这个去重为什么很难理解呢,所谓去重,其实就是使用过的元素不能重复选取。 这么一说好像很简单!

  • 都知道组合问题可以抽象为树形结构,那么“使用过”在这个树形结构上是有两个维度的,一个维度是同一树枝上使用过,一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

  • 那么问题来了,我们是要同一树层上使用过,还是同一树枝上使用过呢?

  • 回看一下题目,元素在同一个组合内是可以重复的,怎么重复都没事,但两个组合不能相同。

  • 所以我们要去重的是同一树层上的“使用过”,同一树枝上的都是一个组合里的元素,不用去重

  • 为了理解去重我们来举一个例子,candidates = [1, 1, 2], target = 3,(方便起见candidates已经排序了)

强调一下,树层去重的话,需要对数组排序!

40.组合总和II

1.递归的参数

  • 和Leetcode39组合一样,需要result存放结果,path存放单条路径
  • sum来存放当前的所有和
  • startindex来标志当前遍历的位置
  • 还需要一个used数组来用于去重,在下面会重点介绍去重!!!

2.递归的结束条件

  • 与上题一样,当sum>=targetSum就返回,如果等于,我们就收集结果

3.单层搜索的逻辑

这里与LeetCode39.组合总和最大的不同就是要去重了。

前面我们提到:要去重的是“同一树层上的使用过”,如何判断同一树层上元素(相同的元素)是否使用过了呢。

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false,就说明:前一个树枝,使用了candidates[i - 1],也就是说同一树层使用过candidates[i - 1]

此时for循环里就应该做continue的操作。

这块比较抽象,如图:

40.组合总和II1

我在图中将used的变化用橘黄色标注上,可以看出在candidates[i] == candidates[i - 1]相同的情况下:

  • used[i - 1] == true,说明同一树枝candidates[i - 1]使用过

  • used[i - 1] == false,说明同一树层candidates[i - 1]使用过

  • 为什么 used[i - 1] == false 就是同一树层呢,因为同一树层,used[i - 1] == false 才能表示,当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。

  • 而 used[i - 1] == true,说明是进入下一层递归,去下一个数,所以是树枝上,如图所示

单层递归的代码如下:

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
    // used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
    // used[i - 1] == false,说明同一树层candidates[i - 1]使用过
    // 要对同一树层使用过的元素进行跳过
    if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
        continue;
    }
    sum += candidates[i];
    path.push_back(candidates[i]);
    used[i] = true;
    backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1:这里是i+1,每个数字在每个组合中只能使用一次
    used[i] = false;
    sum -= candidates[i];
    path.pop_back();
}

代码:

class Solution {
public:
	vector<int> path;
	vector<vector<int> > result;
	void backtracking(vector<int> candidates, int targetSum, int sum, int startindex, vector<bool>& used) {
		if (sum >= targetSum) {
			if (sum == targetSum) result.push_back(path);
			return;
		}
		//这里的剪枝过程在组合总和中有讲到过!
		for (int i = startindex; i < candidates.size() && sum + candidates[i]<=targetSum; i++) {
			//如果是同一层的相同元素,就去重!也就是跳过本轮循环
            // used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false,说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
			if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == 0) continue;
			sum += candidates[i];
			path.push_back(candidates[i]);
			used[i] = 1;
			//要注意这里是i+1,与之前讲解的组合总和不同,这里不能够选取重复的元素
			backtracking(candidates, targetSum, sum, i + 1, used);
			sum -= candidates[i];
			path.pop_back();
			//回溯的时候将之前使用过的元素置为0,标志着这是同一层的元素(树层),而不是树枝上的元素
			used[i] = 0;
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		path.clear(); result.clear();
		if (candidates.size() == 0) return result;
		vector<bool> used(candidates.size(), 0);
		//注意这里一定要排序
		sort(candidates.begin(), candidates.end());
		backtracking(candidates, target, 0, 0, used);
		return result;
	}
};

注意:


版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!

标签:

相关文章

本站推荐

标签云