算法训练营第24天回溯（组合）

  • 开发
  • 15

回溯（组合）

模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

在这里插入图片描述

在这里插入图片描述

第77题. 组合

力扣题目链接(opens new window)

题目

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]

解答

正常方法（不够快，遍历了许多没必要的枝）

一个递归就相当于嵌套了一个for（每个递归都是一个分而治之的过程，第一个for是为了取第一个数，之后每次递归都再取一个）

在这里插入图片描述

class Solution {
	List<List<Integer>> results = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
		backtracking(n,k,1);
		return results;
    }

	void backtracking(int n, int k,int index){
		if (path.size() == k){
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = index; i <= n; i++) {//每个for都是一个单独的横向分支
			path.add(i);
			backtracking(n,k,i + 1);//每个递归都是纵向枝
			path.remove(path.size() - 1);
		}
	}
}
剪枝优化

只是修改了for的终止条件，去除没用的枝

在这里插入图片描述

  1. 已经选择的元素个数：path.size();
  2. 所需需要的元素个数为: k - path.size();
  3. 列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）
  4. 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历
    • 例：如果n = 4， k = 4， 那么只有index = 1这条枝需要保留，i<= 1， 因为此时path为空，所以k - path = 4，故n - (k - path.size()) + 1
class Solution {
	List<List<Integer>> results = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
		backtracking(n,k,1);
		return results;
    }

	void backtracking(int n, int k,int index){
		if (path.size() == k){
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = index; i <= n - (k - path.size()) + 1; i++) {//如果n = 4， k = 4， 那么只有index = 1这条枝需要保留，i<= 1， 因为此时path为空，所以k - path = 4，故n - (k - path.size()) + 1
			path.add(i);
			backtracking(n,k,i + 1);
			path.remove(path.size() - 1);
		}
	}
}

216.组合总和III

力扣题目链接(opens new window)

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

解答

涉及到了两处剪枝

  1. 如果目前相加的和已经大于sum，并且没有达到k个元素，也就意味着后面再加只会更大，剪枝就行了

    if (path.size() == k || sum >= n){//sum >= n是为了求和时的剪枝
    if (sum == n && path.size() == k)
        results.add(new ArrayList<>(path));
    return;
}
//等价于
if (sum > n) return;//对sum剪枝

if (sum == n && path.size() == k){
    results.add(new ArrayList<>(path));
    return;
}

  2. 对个数进行剪枝，与上一个题一样

    for (int i = index; i <= 9 - (k - path.size()) + 1; i++) 
//等价于
if (path.size() > k ) return;//对数量剪枝

class Solution {
	List<List<Integer>> results = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
		backtracking(k,n,1,0);
		return results;
    }

	void backtracking(int k,int n,int index,int sum){
		if (path.size() == k || sum >= n){//sum >= n是为了求和时的剪枝
			if (sum == n && path.size() == k)
				results.add(new ArrayList<>(path));
			return;
		}

		for (int i = index; i <= 9 - (k - path.size()) + 1; i++) {//9 - (k - path.size()) + 1是为了数量不够时的剪枝
			path.add(i);
			backtracking(k,n,i + 1,sum + i);
			path.remove(path.size() - 1);
		}
	}
}

等价形式

class Solution {
	List<List<Integer>> results = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
		backtracking(k,n,1,0);
		return results;
    }

	void backtracking(int k,int n,int index,int sum){

		if (path.size() > k ) return;//对数量剪枝

		if (sum > n) return;//对sum剪枝

		if (sum == n && path.size() == k){
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = index; i <= 9; i++) {
			path.add(i);
			backtracking(k,n,i + 1,sum + i);
			path.remove(path.size() - 1);
		}
	}
}

17.电话号码的字母组合

力扣题目链接(opens new window)

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

在这里插入图片描述

示例:

  • 输入：“23”
  • 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解答

有几个字母深度就是几

注意回溯后的组合一定是无序的，因为会先把最后一个全部找完，再找前一个（不涉及顺序，才能这么回溯）

例：

测试用例：“234”

结果：[adg, adh, adi, aeg, aeh, aei, afg, afh, afi, bdg, bdh, bdi, beg, beh, bei, bfg, bfh, bfi, cdg, cdh, cdi, ceg, ceh, cei, cfg, cfh, cfi]

  1. adg：2的第一个，3的第一个，4的第一个，此时index + 1= 3，达到结束条件，将adg加入
  2. 将最后一个g弹出，进入index = 3的for循环，再次将4对应的第二个h放入path，然后将adh加入
  3. 同理，将adi加入
  4. 此时第三个for已经结束，跳出该循环，第三个递归结束，此时index = 2，并且当前的path中只有ad，然后执行回溯，d再次被弹出
  5. 进入第二个for的第二层，即将3对应的第二个元素e加入，进入递归，此时index没达到4，所以继续进入下一层递归，将4的第一个元素g再加入，即得到aeg
  6. 依次类推
class Solution {
	List<String> result = new ArrayList<>();
	StringBuffer path = new StringBuffer();
    public List<String> letterCombinations(String digits) {
		if (Objects.equals(digits, "") || Objects.equals(digits, " "))
			return result;
		Map<Character,String> map = new HashMap<>();
		map.put('2', "abc");
		map.put('3', "def");
		map.put('4', "ghi");
		map.put('5', "jkl");
		map.put('6', "mno");
		map.put('7', "pqrs");
		map.put('8', "tuv");
		map.put('9', "wxyz");
		backtracking(digits,map,0);
		return result;
    }
	void backtracking(String digits,Map<Character,String> map,int index){
		if (index == digits.length()){
			result.add(path.toString());
			return;
		}

		String element = map.get(digits.charAt(index));
		for (int i = 0; i < element.length(); i++) {
			path.append(element.charAt(i));
			backtracking(digits,map,index + 1);
			path.deleteCharAt(path.length() - 1);//一定是无序的
		}
	}
}

39. 组合总和

力扣题目链接(opens new window)

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1：

  • 输入：candidates = [2,3,6,7], target = 7,
  • 所求解集为： [ [7], [2,2,3] ]

示例 2：

  • 输入：candidates = [2,3,5], target = 8,
  • 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]

解答

巨大误区：

必须要有startIndex参数，只是startIndex的传入参数根据情况不同而不同，但是必须要有，如果没有就会出现重复的元素，也就是可能出现在这里插入图片描述
这种情况，因为如果使用下面的代码，

		for (int i = 0; i < candidates.length; i++) {
			path.add(candidates[i]);
			backtracking(candidates, target, sum + candidates[i], i);
			path.removeLast();//sum在当前这一轮中没有变，也就是相当于已经进行了回溯
		}

也就相当于每次都是从0开始，也就意味着当当前递归函数结束，返回上一层时，上一层重新进入下一层的递归树时，还是会遍历之前已经遍历过的元素，导致重复组合的产生

例：[2,3,6,7] 7

  1. 2 2 2 2 remove
  2. 2 2 2 3 remove
  3. 2 2 2 6 remove
  4. 2 2 2 7 remove
  5. 2 2 3 return
  6. 2 2 6 remove
  7. 2 2 7 remove
  8. 2 3 2出现了重复，因为在当这一轮来说，下一层递归不应该在遍历当前遍历的元素之前的元素，因为在之前已经遍历过了，所以就会出现重复的组合

正确代码应该是

		for (int i = startIndex; i < candidates.length; i++) {
			path.add(candidates[i]);
			backtracking(candidates, target, sum + candidates[i], i);
			path.removeLast();//sum在当前这一轮中没有变，也就是相当于已经进行了回溯
		}

还应该注意必须要排序，因为如果不排序那么使用if (sum > target) return;来剪枝就是错误的

正确代码
class Solution {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
		Arrays.sort(candidates);
		backtracking(candidates,target,0,0);
		return result;
    }

	void backtracking(int[] candidates,int target,int sum,int startIndex){
		if (sum > target) return;//剪枝

		if (sum == target){
			result.add(new LinkedList<>(path));
			return;
		}
		for (int i = startIndex; i < candidates.length; i++) {
			path.add(candidates[i]);
			backtracking(candidates, target, sum + candidates[i], i);
			path.removeLast();//sum在当前这一轮中没有变，也就是相当于已经进行了回溯
		}
	}
}
总结
  1. 一定要是有index，不要想当然的使用for，导致重复元素的产生
  2. 一定要排序，否则剪枝会有问题

40.组合总和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]
]

解答

在这里插入图片描述

树枝去重

backtracking(candidates,target,sum + candidates[i],i + 1);使用i+1来防止树枝遍历相同的元素，也就是防止出现重复元素（由于每个元素只能出现一次，所以为i+1，否则就像上一个题一样为i）

树层去重

if (i > startIndex && candidates[i] == candidates[i - 1]) continue;对于同一层的元素，如果两个元素相同，就直接跳过该轮，否则也会出现重复元素

class Solution {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
		Arrays.sort(candidates);
		backtracking(candidates,target,0,0);
		return result;
    }
	void backtracking(int[] candidates, int target , int sum, int startIndex){
		if (sum > target) return;

		if (sum == target){
			result.add(new ArrayList<>(path));
			return;
		}

		for (int i = startIndex; i < candidates.length; i++) {
			if (i > startIndex && candidates[i] == candidates[i - 1])
				continue;//因为已经排序过，所以要保证同一层的元素不相同，如果相同直接跳过
			//也就是对于path中索引相同位置的元素不能两次一致，这样可能会出现重复的组合
			path.add(candidates[i]);
			backtracking(candidates,target,sum + candidates[i],i + 1);
			path.removeLast();
		}
	}
}

求和总结

  1. 对于不包含重复元素的集合，要想防止出现元素重复的组合，即[2 , 3] [3 , 2]为重复元素的组合，就要使用startIndex来限定 backtracking(candidates,target,sum + candidates[i],i + 1);

    1. 如果是允许同一个元素在组合中多次出现，则使用 backtracking(candidates,target,sum + candidates[i],i + 1);

  2. 对于包含重复元素的集合，除了要是有startIndex外，还需要对树层元素进行判断，否则如果是[1 ,1,2,3]，target = 3，就会出现两个相同的[1,2]，因为对于第一层会遍历两次，使用if (i > startIndex && candidates[i] == candidates[i - 1]) continue;解决

阅读全部

相关推荐

  2. 算法训练营第24天|回溯算法理论基础 LeetCode 77.组合

    2024-04-14 23:34:01       25 阅读

  5. 代码随想录算法训练营第28天|回溯

    2024-04-14 23:34:01       8 阅读

  6. 代码随想录算法训练营第25天|回溯

    2024-04-14 23:34:01       9 阅读

  7. 代码随想录算法训练营第27天|回溯

    2024-04-14 23:34:01       9 阅读

  8. 代码随想录算法训练营第29天|回溯

    2024-04-14 23:34:01       12 阅读

  9. 代码随想录算法训练营第24天|● 理论基础 ● 77. 组合

    2024-04-14 23:34:01       36 阅读

  10. 代码随想录算法训练营第24天|理论基础|77. 组合

    2024-04-14 23:34:01       19 阅读

最近更新

  1. 数据守卫者：sklearn中的异常点检测技术

    2024-04-14 23:34:01       0 阅读

  2. 概率解码：SKlearn中模型的概率预测指南

    2024-04-14 23:34:01       0 阅读

  3. 遇到的问题汇总

    2024-04-14 23:34:01       0 阅读

  4. Oracle中CREATE FORCE VIEW的说明和例子

    2024-04-14 23:34:01       0 阅读

  6. 探索邻近奥秘：SKlearn中K-近邻（KNN）算法的应用

    2024-04-14 23:34:01       0 阅读

  9. 简谈设计模式之工厂模式

    2024-04-14 23:34:01       0 阅读

  10. 深⼊理解 JVM 底层原理、垃圾回收机制，能通过mat、jstat进行JVM参数调优

    2024-04-14 23:34:01       0 阅读

  14. tensorflow学习笔记(二)

    2024-04-14 23:34:01       1 阅读

  16. Typescript【网址取ID传入后端API】

    2024-04-14 23:34:01       1 阅读

  17. mongodb-数据备份和恢复

    2024-04-14 23:34:01       1 阅读

  20. 64、基于去噪卷积神经网络的彩色图像去噪(matlab)

    2024-04-14 23:34:01       1 阅读

热门阅读

  1. leetcode热题HOT 207. 课程表(拓扑排序)

    2024-04-14 23:34:01       14 阅读

  2. 树莓派4B开发板安装Anaconda虚拟环境

    2024-04-14 23:34:01       15 阅读

  3. 博士找教职--经验贴

    2024-04-14 23:34:01       17 阅读

  9. 【备忘】composer国内镜像列表

    2024-04-14 23:34:01       20 阅读

  11. Linux下静态库与动态库使用总结

    2024-04-14 23:34:01       15 阅读

  13. RLHF实践问题记录

    2024-04-14 23:34:01       18 阅读

  14. 感染了后缀为.faust勒索病毒如何应对？数据能够恢复吗？

    2024-04-14 23:34:01       14 阅读

  16. 前端监控告警平台原理,及如何捕捉全局错误,异步promise错误,资源错误,vue错误

    2024-04-14 23:34:01       15 阅读

  18. Rust---模式（Pattern）匹配

    2024-04-14 23:34:01       14 阅读

  20. Lua语法(三)——元表与元方法

    2024-04-14 23:34:01       17 阅读

  21. AK3760编译环境配置 Ubuntu 20.04.6

    2024-04-14 23:34:01       15 阅读