【递归、搜索与回溯算法】穷举、暴搜、深搜、回溯、剪枝

题目描述：

思路讲解：
本道题需要我们从给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。通过递归尝试所有可能的元素排列，在每一步选择一个未使用的元素加入当前排列，完成选择后回溯并尝试下一个元素，直到生成所有完整排列。以下是具体的思路：

• 核心逻辑：
  • 全排列的本质是从数组中依次选择元素，每个元素在排列中只能出现一次。通过递归逐层确定排列的每个位置，使用 “选择 - 递归 - 回溯” 的流程遍历所有可能的组合
• 全局变量：
  • path：当前正在构建的排列
  • isuse：记录元素是否已被使用的布尔数组（避免重复选择）
  • ans：存储所有完整排列的结果集（引用传递）
• 终止条件：
  • 当 path 的长度等于 nums 的长度时，说明已生成一个完整排列，将其加入 ans 并返回
• 递归逻辑：
  • 遍历数组中的每个元素，若元素未被使用（isuse[i] == false）：
    • 将元素加入 path，标记 isuse[i] = true
    • 继续递归构建下一个位置的元素
    • 递归返回后，将元素从 path 中移除，标记 isuse[i] = false，以便其他分支使用该元素

编写代码：

class Solution {vector<vector<int>> ans;bool isuse[7];vector<int> path;int len;
public:void _permute(vector<int>& nums) {if(path.size() == len){ans.push_back(path);return;}for(int i = 0 ; i < len ; i++){if(isuse[i] == false){path.push_back(nums[i]);isuse[i] = true;_permute(nums);path.pop_back();isuse[i] = false;}}}vector<vector<int>> permute(vector<int>& nums) {len = nums.size();memset(isuse,false,sizeof(isuse));_permute(nums);return ans;}
};

题目描述：

思路讲解：
本道题需要我们根据整数数组 nums ，返回该数组所有可能的子集。逐步选择元素，构建所有可能的子集，通过回溯法在每一步决定是否选择当前元素，最终生成所有不重复的子集。

• 核心逻辑：
  • 子集问题的本质是从数组中选择任意个元素（包括 0 个），形成不重复的集合。递归过程中，对于每个元素，有两种选择：加入当前子集或不加入当前子集，通过遍历所有选择组合生成完整解集。
• 全局变量：
  • path：当前正在构建的子集
  • ans：存储所有子集的结果集
• 终止条件：
  • 当遍历完数组所有元素（pos == nums.size()）时，将当前子集 path 加入 ans 并返回。
• 递归逻辑：
  • 不选择当前元素：直接递归处理下一个元素，当前子集不变。
  • 选择当前元素：将 nums[pos] 加入 path，递归处理下一个元素，之后回溯（从 path 中移除该元素）。

编写代码：

class Solution {vector<vector<int>> ans;vector<int> path;int len;
public:void _subsets(vector<int>& nums , int pos) {if(pos == len){ans.push_back(path);return;}path.push_back(nums[pos]);_subsets(nums,pos+1);path.pop_back();_subsets(nums,pos+1);}vector<vector<int>> subsets(vector<int>& nums) {len = nums.size();_subsets(nums,0);return ans;}
};