【回溯Ⅰ】子集问题

2024-08-24 18:12
文章标签 问题 子集 回溯

本文主要是介绍【回溯Ⅰ】子集问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

回溯题集Ⅰ

  • 什么是回溯？
  • 组合问题题集
    • 回溯 and 二进制枚举
      • 78. 子集
        • 二进制枚举
        • 递归求解
      • 77. 组合
        • 递归
        • 二进制枚举
        • ⭐字典序法枚举
      • 216. 组合总和 III
        • 二进制枚举
        • 字典序法枚举
        • 递归

什么是回溯？

回溯是一种算法，通常用于解决搜索问题、游戏问题、布局问题等。在回溯算法中，系统尝试在所有可能的选择中逐步构建解决方案，当发现当前的选择并不是有效的解决方案时，便回溯到之前的步骤，尝试其他的选择。这种方法通过深度优先的方式搜索所有可能的情况，直到找到解决方案或者确定不存在解决方案为止。

回溯算法通常包括以下步骤：

  • 选择：做出一个选择，尝试向前推进。
  • 约束：检查当前选择是否满足问题的限制条件。
  • 目标：检查当前选择是否是期望的解决方案。
  • 回溯：如果选择不满足约束条件或者不能达到期望的解决方案，就回溯到之前的步骤，尝试其他的选择。

这种算法在许多领域都有应用，如解决数独、八皇后问题、图的着色问题等。回溯算法的实现通常使用递归的方式，因为问题的解决方案往往可以表示为一棵树，通过递归的方式遍历这棵树，从而找到解决方案。
深度优先搜索（DFS）在回溯问题中用得很多，是一种常见的解决问题。深度优先搜索可以用递归方式实现，也可以使用栈而避免函数递归调用。
注意：递归函数有几个要点：

  • 函数终止条件：递归函数必须定义清晰的终止条件，也称为基本情况。这些条件应该能够直接返回结果，而不再进行递归调用。缺乏终止条件或者不正确的终止条件可能导致无限递归，最终耗尽系统资源。

  • 递归关系：递归函数根据递归关系，去递归调用自身。递归关系使得函数朝终止条件逐步推进，以确保递归最终结束。

组合问题题集

回溯 and 二进制枚举

下面的几个题目，是一个类型，可以用经典的回溯递归解决，也可以用二进制枚举。
什么是二进制枚举，最经典易懂的例子，一个集合假设有n个元素，其幂集有2^n个，这是怎么得到的？——n个元素，每个元素有两种可能（不存在子集中 OR 存在子集中），每个位置2*2*2*…*2，就是2^n。 二进制枚举法，对于78.子集就是完美适配的解决方案。 用一个mask：从00000逐一增加到11111即可表示所有的可能性。 在其他约束情况下，需增加一步判断：判断这些子集是否满足约束条件。

78. 子集

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
在这里插入图片描述

二进制枚举

数组nums有n个元素，那么其幂集就有2^n个，1左移n位，就是2^n。下面是二进制运算的一些细节：

  • 细节1：用mask来表示这个二进制枚举的过程，mask就从0逐一增加到(1<<n)。
  • 细节2：根据mask的二进制表示的每一位i，判断nums[i]是否在某子集中，mask的第i位通过mask & (1<<i)，或者（mas>>i)&1得到，再判断第i位为0还是1。

java代码如下：

class Solution {public List<List<Integer>> subsets(int[] nums) {List<Integer> temp = new ArrayList<Integer>();List<List<Integer>> ans = new ArrayList<List<Integer>>();int n = nums.length;// mask表示所有可能的二进制掩码for(int mask = 0; mask < (1 << n); mask++){temp.clear();// 判断mask的每一位for(int i = 0; i < n ; i ++){//if(((mask >> i) & 1)!= 0)if((mask & (1 << i)) != 0)temp.add(nums[i]);}// 注意java是面向对象的编程语言，这里的ArrayList是引用型//如果直接ans.add(temp)，后续temp还会更改，ans中这个子集也会更改，结果就不正确了//因此需要new一个新的add到ans中ans.add(new ArrayList<Integer>(temp));}return ans;        }
}
递归求解

整体是思路是遍历数组nums，每一个元素有两种可能：选择OR不选择。根据前面提到的递归函数的两个要点，分别分析：

  • 首先是递归结束条件，我们是在遍历数组nums，因此数组遍历结束即递归结束。用cur表示遍历到元素下标，cur从0开始，如果cur == n，即遍历结束
  • 其次是递推关系，每一轮针对下标cur的元素操作（选择OR不选择），就去判断cur++的元素，直到cur == n。
    这里有一个大致模板（C++版本），借鉴的力扣官方题解：
vector<int> t;
void dfs(int cur, int n) {if (cur == n) {// 记录答案...return;}// 考虑选择当前位置t.push_back(cur);dfs(cur + 1, n, k);t.pop_back();// 考虑不选择当前位置dfs(cur + 1, n, k);
}

下面是Java版本的完整解决代码：

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();public List<List<Integer>> subsets(int[] nums) {dfs(0,nums);return ans;}public void dfs(int cur, int[] nums){if( cur == nums.length){ans.add(new ArrayList<Integer>(temp));return ;}temp.add(nums[cur]); //考虑下标cur元素在该子集中的情况dfs(cur + 1, nums);temp.remove(temp.size() -1); // 考虑下标cur元素不在该子集中的情况dfs(cur + 1, nums);}
}

77. 组合

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
在这里插入图片描述

递归

这里的数组nums就是[1~n]，我们的目标是找到只有k个元素的集合。我们用之前找所有子集的代码模板，但是递归结束有两种可能：①已经有k个元素了，找到答案直接返回；②遍历完了整个数组了。 其实①是一种剪枝，即前面1~cur 的元素中已经包括k个元素了，cur后面元素涉及到的搜索空间就不探索了。

// 找到只包含k个元素的子集
if (temp.size() == k) {ans.push_back(temp);return;}
// 遍历完数组[1,2,3,...,n]
if (cur == n + 1) {return;}

还有一种可能：1~cur中只选择了m个元素，cur之后元素只有s个，而m+s< k，那么也可以直接忽略这种情况，因为这种情况下即便遍历完数组也找不到k个元素的集合了。

// 就算cur~n所有元素都选上，这个子集的元素也少于k个
if(temp.size() + (n - cur + 1) < k){return
}

有了这种情况 cur == n+1（遍历结束）这个约束条件可以删除。 因为1~cur中被选择的元素m个，可以明确m<=k。当m ==k时，已经被第一个约束条件结束递归了；如果cur == n+1的时候，m<k，那么早在cur=n+1之前就被第三个约束条件剪枝了。

Java代码如下：

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();public List<List<Integer>> combine(int n, int k) {dfs(1, n, k);return ans;}public void dfs(int cur, int n , int k){if(temp.size() + (n - cur + 1) < k)return ;if(temp.size() == k){ans.add(new ArrayList<Integer>(temp));return ;}temp.add(cur); // 选择当前元素的情况dfs(cur + 1, n, k);temp.remove(temp.size() - 1); // 不选择当前元素的情况dfs(cur + 1, n, k);}
}
二进制枚举

用二进制枚举找所有子集，增加一个子集元素数量为k的判断即可。

class Solution {List<Integer> temp = new ArrayList<Integer>();List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> combine(int n, int k) {// 利用mask找到所有的子集（幂集）for(int mask = 0; mask < (1<<n); mask++ ){temp.clear();for(int i = 0; i < n; i++)if( (mask & (1<<i)) != 0)temp.add(i+1);// 判断该子集元素个数是否满足要求（k个）if(temp.size()==k)ans.add(new ArrayList<Integer>(temp));}return ans;}
}
⭐字典序法枚举

上面用二进制枚举法，遍历了所有的子集，这是没有必要的，因为我们只需要仅包括k个元素的子集。
那么只包括k个元素，即n位的mask，只有k个位置为1。我们要怎么得到这些mask呢？——用字典序列。 比如6位的mask只有3位为1，从000111开始：000111→001011→001101→001110→010011→010101→010110→011001→011010→011100→100011……→111000
初始时二进制掩码的最低k位全为1，最终结束的时候是mask最高k位全为1。代码如何实现这个字典序列变化的过程呢？ 首先我们用一个长度为k+1的数组temp表示结果数组，初始赋值为[1,2,3,…,k,n+1]，最后一位是哨兵位，用于最后判断遍历结束。 如果temp[j] + 1 ≠ temp[ j + 1]，说明temp[j]和temp[j+1]不连续，即二进制掩码的第temp[j]和temp[j+1]位为1，且不连续。那么二进制掩码中temp[j]位的1可以向高位移动一维，对应temp数组中temp[j] = temp[j] +1；而mask中temp[j]位之后的1全部移动到最低位，对应temp数组中下标0~j-1的数变成[1,2,3,…,j-1]。
完整Java代码如下：

class Solution {List<Integer> temp = new ArrayList<Integer>();List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> combine(int n, int k) {// 将 temp 中 [0, k - 1] 每个位置 i 设置为 i + 1，即 [0, k - 1] 存 [1, k]for (int i = 1; i <= k; ++i) {temp.add(i);}temp.add(n + 1); // 末尾加一位 n + 1 作为哨兵int j = 0;while (j < k) {ans.add(new ArrayList<Integer>(temp.subList(0, k)));j = 0;// 寻找第一个 temp[j] + 1 != temp[j + 1] 的位置 t// 我们需要把 [0, j- 1] 区间内的每个位置重置成 [1, j]while (j < k && temp.get(j) + 1 == temp.get(j + 1)) {temp.set(j, j + 1);++j;}// j 是第一个 temp[j] + 1 != temp[j + 1] 的位置temp.set(j, temp.get(j) + 1);}return ans;}
}

216. 组合总和 III

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
在这里插入图片描述
这里的数组nums就是[1,2,3,4,5,6,7,8,9]，要求是找包括k个元素且元素和为n的子集。

二进制枚举

我们可以枚举[1~9]所有子集，但是增加两个判断条件：①只包括k个元素；②元素和为n。

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();public List<List<Integer>> combinationSum3(int k, int n) {  for(int mask = 0 ; mask < (1 << 9); mask++){if(check(mask,k,n))ans.add(new ArrayList<Integer>(temp));}return ans;}public boolean check(int mask,int k,int n){temp.clear();for(int i = 0; i < 9 ; i++){if(((mask>>i) & 1) != 0 )temp.add(i+1);}// 先判断元素数量是否为kif(temp.size() != k)return false;int sum = 0;for(int num : temp)sum += num;return n == sum; // 再判断和是否为sum}
}
字典序法枚举

这里遍历判断所有的子集，其实是有浪费时间的，因为我们只需要k个元素的子集，再去判断其和即可。 因此可以用上述77题的方法，只找k个元素的子集，再增加一个sum == n的判断：

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();public List<List<Integer>> combinationSum3(int k, int n) { int sum =0; // 记录包含k个元素的子集的和for(int i = 0;i < k; i++){temp.add(i+1);sum += i+1;}temp.add(10);int j = 0;while(j < k){if(sum==n){ // 新增判断条件ans.add(new ArrayList<Integer>(temp.subList(0,k)));}j = 0;while(j < k && temp.get(j)+1 == temp.get(j+1)){   sum -=  temp.get(j);          temp.set(j,j+1);sum += j+1;j++;                }temp.set(j,temp.get(j)+1);sum += 1;           }return ans;}
}
递归

这里要遍历的数是1~9，依旧是上面的模板，dfs遍历每个数的时候都有两种情况：选择OR不选择。 递归结束条件是：找到了包括k个元素的子集，如果子集元素和为n就添加这个temp到结果数组中，否则什么也不做：

class Solution {List<Integer> temp = new ArrayList<Integer>();List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> combinationSum3(int k, int n) {dfs(1, 9, k, n);return ans;}public void dfs(int cur, int n, int k, int sum) {// 剪枝if (temp.size() + (n - cur + 1) < k) {return;}// 递归结束if (temp.size() == k) {int tempSum = 0;for (int num : temp) {tempSum += num;}// 判断和是否满足条件if (tempSum == sum) {ans.add(new ArrayList<Integer>(temp));   }return;}temp.add(cur); //子集中添加curdfs(cur + 1, n, k, sum);temp.remove(temp.size() - 1); // 子集中不添加curdfs(cur + 1, n, k, sum);}
}

👇另一种递归思路
之前是遍历数组，以数组遍历结束为递归结束条件。现在递归结束条件是找到包括k个元素的子集，同时满足和为n。 递推关系：前一轮temp[j] = a，那么temp[j+1]可以在[a+1~9]之间选择。实际上temp[0]可以在[1~9]中任意选择，假设temp[0] = 3，就默认1、2不会出现在这个子集中。完整代码如下：

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> output = new ArrayList<Integer>();public List<List<Integer>> combinationSum3(int k, int n) {       backstrack(1,0,k,n,0);return  ans;  }public void backstrack(int loca, int num,  int k ,int n, int sum){if(num + (9 - loca +1) < k)return ;// k个数且和为n，加入该组合并返回if(num == k && sum == n){ans.add(new ArrayList<Integer>(output));return ;}// k个数，但是和不会n，直接返回if( num == k)return ;// 和为n但是不够k个数，直接返回if(sum == n)return ;// 既不够k个数，和也不够n，继续递归寻找for(int i = loca; i <= 9; i++){if(sum + i <= n){output.add(i);backstrack(i + 1, num + 1, k, n, sum + i);output.remove(num);}}}
}

实际这两种递归思路的区别在于，之前一种是在遍历数组[1~9]，判断nums[i]选择or不选择；现在是递归k次，确定找长度为k的子集，temp[i]可以在[temp[i-1] + 1~9]之间任意选择。

这篇关于【回溯Ⅰ】子集问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1103222。

相关文章

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
缓存雪崩问题

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库，瞬间耗尽数据库资源，导致数据库无法使用。 解决方案： 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内，大量缓存数据同时失效，导致所有请求直接涌向数据库，瞬间增加数据库的负载压力，可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【VUE】跨域问题的概念，以及解决方法。

【VUE】跨域问题的概念，以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略，该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同，则需要服务器显式地允许这种跨域请求。一般在springbo
阅读更多...
题目1254：N皇后问题

题目1254：N皇后问题

题目1254：N皇后问题 时间限制：1 秒 内存限制：128 兆 特殊判题：否 题目描述： N皇后问题，即在N*N的方格棋盘内放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在同一斜线上。因为皇后可以直走，横走和斜走如下图)。 你的任务是，对于给定的N，求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入
阅读更多...
vscode中文乱码问题，注释，终端，调试乱码一劳永逸版

vscode中文乱码问题，注释，终端，调试乱码一劳永逸版

忘记咋回事突然出现了乱码问题，很多方法都试了，注释乱码解决了，终端又乱码，调试窗口也乱码，最后经过本人不懈努力，终于全部解决了，现在分享给大家我的方法。 乱码的原因是各个地方用的编码格式不统一，所以把他们设成统一的utf8. 1.电脑的编码格式 开始-设置-时间和语言-语言和区域 管理语言设置-更改系统区域设置-勾选Bata版：使用utf8-确定-然后按指示重启 2.vscode
阅读更多...
Android Environment 获取的路径问题

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR
阅读更多...
form表单提交编码的问题

form表单提交编码的问题

浏览器在form提交后，会生成一个HTTP的头部信息"content-type"，标准规定其形式为Content-type: application/x-www-form-urlencoded; charset=UTF-8        那么我们如果需要修改编码，不使用默认的，那么可以如下这样操作修改编码，来满足需求： hmtl代码：   <meta http-equiv="Conte
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2