【回溯Ⅰ】子集问题

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。

相关文章

IDEA和GIT关于文件中LF和CRLF问题及解决

IDEA和GIT关于文件中LF和CRLF问题及解决

《IDEA和GIT关于文件中LF和CRLF问题及解决》文章总结：因IDEA默认使用CRLF换行符导致Shell脚本在Linux运行报错,需在编辑器和Git中统一为LF,通过调整Git的core.aut... 目录问题描述问题思考解决过程总结问题描述项目软件安装shell脚本上git仓库管理，但拉取后，上l
阅读更多...
idea npm install很慢问题及解决(nodejs)

idea npm install很慢问题及解决(nodejs)

《ideanpminstall很慢问题及解决(nodejs)》npm安装速度慢可通过配置国内镜像源（如淘宝）、清理缓存及切换工具解决,建议设置全局镜像（npmconfigsetregistryht... 目录idea npm install很慢(nodejs)配置国内镜像源清理缓存总结idea npm in
阅读更多...
pycharm跑python项目易出错的问题总结

pycharm跑python项目易出错的问题总结

《pycharm跑python项目易出错的问题总结》：本文主要介绍pycharm跑python项目易出错问题的相关资料,当你在PyCharm中运行Python程序时遇到报错,可以按照以下步骤进行排... 1. 一定不要在pycharm终端里面创建环境安装别人的项目子模块等，有可能出现的问题就是你不报错都安装
阅读更多...
idea突然报错Malformed \uxxxx encoding问题及解决

idea突然报错Malformed \uxxxx encoding问题及解决

《idea突然报错Malformeduxxxxencoding问题及解决》Maven项目在切换Git分支时报错,提示project元素为描述符根元素,解决方法：删除Maven仓库中的resolv... 目www.chinasem.cn录问题解决方式总结问题idea 上的 maven China编程项目突然报错，是
阅读更多...
Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题

Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题

《Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题》在爬虫工程里,“HTTPS”是绕不开的话题,HTTPS为传输加密提供保护,同时也给爬虫带来证书校验、... 目录一、核心问题与优先级检查（先问三件事）二、基础示例：requests 与证书处理三、高并发选型：
阅读更多...
前端导出Excel文件出现乱码或文件损坏问题的解决办法

前端导出Excel文件出现乱码或文件损坏问题的解决办法

《前端导出Excel文件出现乱码或文件损坏问题的解决办法》在现代网页应用程序中,前端有时需要与后端进行数据交互,包括下载文件,：本文主要介绍前端导出Excel文件出现乱码或文件损坏问题的解决办法,... 目录1. 检查后端返回的数据格式2. 前端正确处理二进制数据方案 1：直接下载（推荐）方案 2：手动构造
阅读更多...
Python绘制TSP、VRP问题求解结果图全过程

Python绘制TSP、VRP问题求解结果图全过程

《Python绘制TSP、VRP问题求解结果图全过程》本文介绍用Python绘制TSP和VRP问题的静态与动态结果图,静态图展示路径,动态图通过matplotlib.animation模块实现动画效果... 目录一、静态图二、动态图总结【代码】python绘制TSP、VRP问题求解结果图（包含静态图与动态图
阅读更多...
MyBatis/MyBatis-Plus同事务循环调用存储过程获取主键重复问题分析及解决

MyBatis/MyBatis-Plus同事务循环调用存储过程获取主键重复问题分析及解决

《MyBatis/MyBatis-Plus同事务循环调用存储过程获取主键重复问题分析及解决》MyBatis默认开启一级缓存,同一事务中循环调用查询方法时会重复使用缓存数据,导致获取的序列主键值均为1,... 目录问题原因解决办法如果是存储过程总结问题myBATis有如下代码获取序列作为主键IdMappe
阅读更多...
k8s容器放开锁内存限制问题

k8s容器放开锁内存限制问题

《k8s容器放开锁内存限制问题》nccl-test容器运行mpirun时因NCCL_BUFFSIZE过大导致OOM,需通过修改docker服务配置文件,将LimitMEMLOCK设为infinity并... 目录问题问题确认放开容器max locked memory限制总结参考：https://Access
阅读更多...
Java中字符编码问题的解决方法详解

Java中字符编码问题的解决方法详解

《Java中字符编码问题的解决方法详解》在日常Java开发中,字符编码问题是一个非常常见却又特别容易踩坑的地方,这篇文章就带你一步一步看清楚字符编码的来龙去脉,并结合可运行的代码,看看如何在Java项... 目录前言背景：为什么会出现编码问题常见场景分析控制台输出乱码文件读写乱码数据库存取乱码解决方案统一使
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2