devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

递归专题训练详解（回溯，剪枝，深度优先）_如何训练递归

作者：我家小花儿 | 2024-04-16 12:51:58

赞

踩

如何训练递归

1.汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

  1. //确定子问题处理方式是相同的
  2. //确定递归函数的函数头传参
  3. //确定函数体也就子问题的处理方式
  4. //判断函数出口
  5.  
  6. class Solution {
  7. public:
  8.     void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
  9.         int n=A.size();
  10.         dfs(A,B,C,n);
  11.     }
  12.  
  13.     void dfs(vector<int>& A,vector<int>&B ,vector<int>& C,int n){
  14.         if(n==1){
  15.         C.push_back(A.back());//这里一定是要A.back(),可以画一下递归展开图
  16.         A.pop_back();
  17.         return;
  18.         }//函数出口
  19.  
  20.         dfs(A,C,B,n-1);//不关心如何递归下去的，认为该函数一定能够帮我做到把a上的n-1数据借助c挪动b上
  21.  
  22.         C.push_back(A.back());//这里一定是要A.back(),可以画一下递归展开图
  23.         A.pop_back();
  24.  
  25.         dfs(B,A,C,n-1);//同样认为该函数一定能把b上残留的n-1个数据借助a放到c上面
  26.     }
  27. };

2.合并升序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
  14.         ListNode* newHead=merge(list1,list2);
  15.         return newHead;
  16.     }
  17.  
  18.     ListNode* merge(ListNode* l1,ListNode* l2){
  19.         if(l1==nullptr) return l2;
  20.         if(l2==nullptr) return l1;
  21.  
  22.  
  23.         if(l1->val<l2->val){
  24.             l1->next=merge(l1->next,l2);
  25.             return l1;//返回拼好的头节点
  26.         }
  27.  
  28.         else{
  29.             l2->next=merge(l2->next,l1);
  30.             return l2;
  31.         }
  32.  
  33.     }
  34. };

3. 反转链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* reverseList(ListNode* head) {
  14.         if(head==nullptr||head->next==nullptr)return head;
  15.         ListNode* newhead=reverseList(head->next);//认为一定可以返回一个已经逆序的子链表
  16.         head->next->next=head;//让已经逆序的子序列的头节点指向子序列的上一个头节点
  17.         head->next=nullptr;
  18.         return newhead;//这里newhead一直是没有移动过的，一直都是新的链表的头结点。
  19.     }
  20. };

4. 两两交换链表中的节点

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* swapPairs(ListNode* head) {
  14.         if(head==nullptr||head->next==nullptr)
  15.         {
  16.             return head;
  17.         }
  18.  
  19.         ListNode* new_head=head->next;
  20.         ListNode* tmp=head->next->next;//小心中途修改的问题
  21.         head->next->next=head;
  22.         head->next=swapPairs(tmp);
  23.         return new_head;
  24.     }
  25. };

5. Pow（x,n）

  • -100.0 < x < 100.0
  • -2^31 <= n <= 2^31-1
  • -10^4 <= x^n <= 10^4

本题需要注意负数的情况和超int取值范围的情况

这样会语法报错。。。

  1. class Solution {
  2. public:
  3.     double myPow(double x, int n) 
  4.     {
  5.         return n > 0 ?pow(x,n) : 1.0/pow(x,-(long long)n );
  6.     }
  7.  
  8.     double pow(double x,long long n)
  9.     {
  10.         if(n==0) return 1.0;
  11.  
  12.         double ret=pow(x,n/2);
  13.  
  14.         if(n%2==0){return ret*ret;}
  15.         else{return ret*ret*x;}
  16.     }
  17. };

6. 布尔逻辑二叉树

  1. class Solution {
  2. public:
  3.     bool evaluateTree(TreeNode* root) {
  4.         if(root->left==nullptr)
  5.         {
  6.             if(root->val==1)return true; 
  7.             else return false;
  8.         }
  9.  
  10.         bool left=evaluateTree(root->left);
  11.         bool right=evaluateTree(root->right);
  12.         if(root->val==2)
  13.         {
  14.             return left || right;
  15.         }
  16.         else 
  17.         {
  18.             return left && right;
  19.         }
  20.  
  21.     }
  22. };

7.根到叶子之和 

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

  • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12.  
  13. //函数头设计，我们认为传入一个节点，那么就会算出此节点到所有节点的数字之和
  14. //函数体：从上一层获得此前的所有数字组合再拼上此层，所以需要多设计一个参数来记录
  15. //函数出口：当没有孩子的时候
  16. class Solution {
  17. public:
  18.     int sumNumbers(TreeNode* root) {
  19.         return dfs(root,0);
  20.     }
  21.  
  22.     int dfs(TreeNode* root,int presum)
  23.     {
  24.         // if(root==nullptr)
  25.         // {
  26.         //     return presum;题目给的一定是有一个节点
  27.         // }
  28.  
  29.         presum=presum*10+root->val;
  30.         std::cout<<presum<<std::endl;
  31.         int ret=0;//因为函数的功能是用来计算之和并返回，所以不能直接presum传入，此处presum只是用于记录已经遍历了的数字。
  32.  
  33.         if(root->left==nullptr&&root->right==nullptr){
  34.             return presum;
  35.         }
  36.  
  37.         if(root->left) ret+=dfs(root->left,presum);
  38.         if(root->right) ret+= dfs(root->right,presum);
  39.  
  40.         return ret;
  41.     }
  42. };

8.二叉树剪枝

给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。

节点 node 的子树为 node 本身，以及所有 node 的后代。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. //函数体设计
  13. //返回一个已经剪枝的根节点
  14.  
  15. //函数出口：当自己是空的时候返回空，处理动作一致
  16.  
  17. class Solution {
  18. public:
  19.     TreeNode* pruneTree(TreeNode* root) {
  20.         // if(root==nullptr)
  21.         // {
  22.         //     return nullptr;
  23.         // }
  24.  
  25.         if(root->left) root->left=pruneTree(root->left);
  26.         if(root->right) root->right=pruneTree(root->right);
  27.  
  28.         if(root->left==nullptr&&root->right==nullptr&&root->val==0)
  29.         //走到头才算是树枝当树枝被剪完了自己也就是树枝的。
  30.         {
  31.             //delete root;
  32.             root=nullptr;
  33.             // return nullptr;
  34.         }
  35.  
  36.         return root;
  37.     }
  38. };

9.验证二叉搜索树（注意剪枝）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14. long long prev_val=LONG_MIN;
  15.  
  16.     bool isValidBST(TreeNode* root) {
  17.         if(root==nullptr)
  18.         {
  19.             return true;
  20.         }
  21.         bool left=isValidBST(root->left);
  22.  
  23.         if(left==false) return false;//剪枝
  24.         
  25.         bool cur=false;
  26.         if(root->val>prev_val)
  27.         {
  28.             prev_val=root->val;
  29.             cur=true;
  30.         }
  31.  
  32.         if(right==false) return false;//剪枝
  33.  
  34.         bool right=isValidBST(root->right);
  35.         //cout<< root->val;
  36.  
  37.  
  38.  
  39.         return left&&right&&cur;
  40.     }
  41. };

10. 二叉搜索树第k小的元素（二叉搜索树中序遍历是一个有序序列）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int count;
  15.     int ret;
  16.  
  17.     int kthSmallest(TreeNode* root, int k) {
  18.         count=k;
  19.         return dfs(root);
  20.     }
  21.  
  22.     int dfs(TreeNode* root)
  23.     {
  24.         if(root==nullptr){
  25.             return ret;
  26.         }
  27.         ret=dfs(root->left);
  28.         if(count==0)
  29.         {
  30.             return ret;
  31.         }
  32.         ret=root->val;
  33.         count--;
  34.         ret=dfs(root->right);
  35.  
  36.         return ret;
  37.     }
  38. };

11. 二叉树的所有路径

12. 全排列

1.此处path设置为全局变量更好，虽然回溯时需要修改，但是节省一些空间并且效率更高。：

  1. class Solution {
  2. public:
  3.  
  4.     vector<vector<int>> ret;
  5.     vector<bool> check;//用于记录哪些数字使用过了而达到剪枝的效果，回溯的时候需要把使用过的数字还回去
  6.     vector<int> path;//这里的path最好使用全局变量
  7.     vector<vector<int>> permute(vector<int>& nums) {
  8.         check.resize(nums.size());
  9.         dfs(nums,path);
  10.         return ret;
  11.     }
  12.  
  13.     void dfs(vector<int>& nums,vector<int> path)
  14.     {
  15.         if(nums.size()==path.size())
  16.         {
  17.             ret.push_back(path);
  18.             return ;
  19.         }
  20.  
  21.         for(int i=0;i<nums.size();i++)
  22.         {
  23.  
  24.  
  25.             if(check[i]==true)
  26.             {
  27.                 continue;
  28.             }
  29.             check[i]=true;
  30.             vector<int> tmp=path;
  31.             tmp.push_back(nums[i]);
  32.             dfs(nums,tmp);
  33.  
  34.             check[i]=false;
  35.         }
  36.     }
  37. };

2. 修改后：

  1. class Solution {
  2. public:
  3.  
  4.     vector<vector<int>> ret;
  5.     vector<bool> check;//用于记录哪些数字使用过了而达到剪枝的效果，回溯的时候需要把使用过的数字还回去
  6.     vector<int> path;//这里的path最好使用全局变量
  7.     vector<vector<int>> permute(vector<int>& nums) {
  8.         check.resize(nums.size());
  9.         dfs(nums,path);
  10.         return ret;
  11.     }
  12.  
  13.     void dfs(vector<int>& nums,vector<int>& path)
  14.     {
  15.         if(nums.size()==path.size())
  16.         {
  17.             ret.push_back(path);
  18.             return ;
  19.         }
  20.  
  21.         for(int i=0;i<nums.size();i++)
  22.         {
  23.  
  24.  
  25.             if(check[i]==true)
  26.             {
  27.                 continue;
  28.             }
  29.             check[i]=true;
  30.             // vector<int> tmp=path;
  31.             // tmp.push_back(nums[i]);
  32.             path.push_back(nums[i]);
  33.             dfs(nums,path);
  34.  
  35.             check[i]=false;//向下递归完后恢复现场
  36.             path.pop_back();
  37.         }
  38.     }
  39. };

13. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

13. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<string> ret;
  15.     string path;
  16.     int i=0;
  17.     vector<string> binaryTreePaths(TreeNode* root) 
  18.     {
  19.         if(root==nullptr) return ret;//假设会传入空，最好不要写在dfs函数里面
  20.         dfs(root,path);
  21.         return ret;
  22.     }
  23.  
  24.     void dfs(TreeNode* root,string path)
  25.     {
  26.         path+=to_string(root->val);
  27.         if(root->left==nullptr&&root->right==nullptr)
  28.         {
  29.             ret.push_back(path);
  30.             return;
  31.         }
  32.         path+="->";
  33.         if(root->left) dfs(root->left,path);
  34.         if(root->right) dfs(root->right,path);//剪枝，并且达到了不会传入空的效果
  35.  
  36.     }
  37. };

14. 子集

  1. class Solution {
  2. public:
  3.     vector<vector<int>> ret;
  4.     vector<int> path;
  5.     //vector<bool> check;
  6.     vector<vector<int>> subsets(vector<int>& nums) 
  7.     {
  8.         dfs(nums,0);
  9.         return ret;
  10.     }
  11.  
  12.     void dfs(vector<int>& nums ,int pos)
  13.     {
  14.         ret.push_back(path);
  15.  
  16.         for(int i=pos;i<nums.size();i++)
  17.         {
  18.             path.push_back(nums[i]);
  19.             dfs(nums,i+1);
  20.             path.pop_back();
  21.         }
  22.  
  23.     }
  24. };

15. 异或和按位或分清楚

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  1. class Solution {
  2. public:
  3.     int ret;//返回值总和
  4.  
  5.     int tmp=0;//记录当前层异或的值
  6.     int subsetXORSum(vector<int>& nums) {
  7.         dfs(nums,0);
  8.         return ret;
  9.     }
  10.  
  11.     void dfs(vector<int>& nums,int pos)
  12.     {
  13.         ret+=tmp;
  14.         for(int i=pos;i<nums.size();i++)
  15.         {
  16.             tmp^=nums[i];
  17.  
  18.             dfs(nums,i+1);
  19.  
  20.             tmp^=nums[i];
  21.         }
  22.     }
  23. };

16. 全排列 ||

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  1. class Solution {
  2. public:
  3.     vector<vector<int>> ret;
  4.     vector<bool> check;
  5.     vector<int> path;
  6.     vector<vector<int>> permuteUnique(vector<int>& nums) {
  7.         sort(nums.begin(),nums.end());
  8.         check.resize(nums.size(),false);
  9.         //没有上句会报错Line 84: Char 2: runtime error: store to null pointer of type 'std::_Bit_type' (aka 'unsigned long') (stl_bvector.h)
  10.         dfs(nums);
  11.         return ret;
  12.     }
  13.  
  14.     void dfs(vector<int>& nums)
  15.     {
  16.         if(path.size()==nums.size())
  17.         {
  18.             ret.push_back(path);
  19.             return;
  20.         }
  21.  
  22.         for(int i=0;i<nums.size();i++)
  23.         {
  24.  
  25.  
  26.             if(check[i]==true ||( i!=0 && nums[i]==nums[i-1] && check[i-1] == false ))
  27.             //check[i-1]==false;说明nums[i]和nums[i-1]同层进行判断比较。
  28.             {
  29.                 continue;
  30.             }
  31.             
  32.             check[i]=true;
  33.             path.push_back(nums[i]);
  34.             dfs(nums);
  35.             check[i]=false;
  36.             path.pop_back();
  37.         }
  38.     }
  39. };

17. 电话号码

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  1. class Solution {
  2. public:
  3.     vector<string> ret;
  4.     string path;
  5.     vector<string> hash={" ", " ", "abc", "def", "ghi","jkl","mno","pqrs","tuv","wxyz"};
  6.  
  7.     vector<string> letterCombinations(string digits) 
  8.     {
  9.         if(digits.size()==0){
  10.             return ret;
  11.         }
  12.         dfs(digits,0);
  13.         return ret;
  14.     }
  15.  
  16.     void dfs(string& digits,int pos)
  17.     {
  18.  
  19.         if(path.size()==digits.size())
  20.         {
  21.             ret.push_back(path);
  22.             return;
  23.         }
  24.  
  25.         for(auto a: hash[digits[pos]-'0'] )
  26.         {
  27.             path.push_back(a);
  28.             dfs(digits,pos+1);
  29.             path.pop_back();
  30.         }
  31.     }
  32. };

18. 括号生成

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  1. class Solution {
  2. public:
  3.     int max;
  4.     int left,right;
  5.     vector<string> ret;
  6.     string path;
  7.     vector<string> generateParenthesis(int n)
  8.     {
  9.         max=n;
  10.         dfs();
  11.         return ret;
  12.     }
  13.  
  14.     void dfs()
  15.     {
  16.         if(right == max)
  17.         {
  18.             ret.push_back(path);
  19.             return;
  20.         }
  21.  
  22.         if(left < max)
  23.         {
  24.             path.push_back('(');
  25.             ++left;
  26.             dfs();
  27.             --left;
  28.             path.pop_back();
  29.         }
  30.  
  31.         if(right < left)
  32.         {
  33.             path.push_back(')');
  34.             right++;
  35.             dfs();
  36.             right--;
  37.             path.pop_back();
  38.         }
  39.     }
  40. };

19. 组合

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  1. class Solution {
  2. public:
  3.     int max;
  4.     vector<int> path;
  5.     vector<vector<int>> ret;
  6.     vector<vector<int>> combine(int n, int k) {
  7.         max=k;
  8.         dfs(1,n);
  9.         return ret;
  10.     }
  11.  
  12.     void dfs(int pos,int& n)
  13.     {
  14.         if(path.size() == max )
  15.         {
  16.             ret.push_back(path);
  17.             return;
  18.         }
  19.  
  20.         for(int i=pos;i<n+1;++i)
  21.         {
  22.             path.push_back(i);
  23.             dfs(i+1,n);//是要传入i+1而不是pos+1
  24.             path.pop_back();
  25.         }
  26.     }
  27. };

20.目标和

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

注意单单int的反复加加减减还是非常耗时的，这里不是拷贝一个vector之类的对象，所以反而恢复现场的操作会更慢从而超时。

  1. class Solution {
  2. public:
  3.     // int ret=0;
  4.     // int path;
  5.     // int now_target;
  6.     // int findTargetSumWays(vector<int>& nums, int target) 
  7.     // {
  8.     //     now_target=target;
  9.     //     dfs(0,1,nums);
  10.     //     return ret;
  11.  
  12.     // }
  13.  
  14.     // void dfs(int pos,int level,vector<int>& nums)
  15.     // {
  16.     //     if(nums.size()+1 == level)
  17.     //     {
  18.     //         if(path==now_target)
  19.     //         {
  20.     //             ret++;
  21.     //         }
  22.     //         return;
  23.     //     }
  24.  
  25.     //     {
  26.     //         path+=nums[pos];
  27.     //         dfs(pos+1,level+1,nums);
  28.     //         path-=nums[pos];
  29.     //     }
  30.  
  31.     //     {
  32.     //         path-=nums[pos];
  33.     //         dfs(pos+1,level+1,nums);
  34.     //         path+=nums[pos];
  35.     //     }
  36.     // }
  37.     int ret=0;
  38.     //int path;
  39.     int now_target;
  40.     int findTargetSumWays(vector<int>& nums, int target) 
  41.     {
  42.         int path=0;
  43.         now_target=target;
  44.         dfs(0,1,nums,path);
  45.         return ret;
  46.  
  47.     }
  48.  
  49.     void dfs(int pos,int level,vector<int>& nums,int path)
  50.     {
  51.         if(nums.size()+1 == level)
  52.         {
  53.             if(path==now_target)
  54.             {
  55.                 ret++;
  56.             }
  57.             return;
  58.         }
  59.  
  60.         {
  61.             //path+=nums[pos];
  62.             dfs(pos+1,level+1,nums,path+nums[pos]);
  63.             //path-=nums[pos];
  64.         }
  65.  
  66.         {
  67.             dfs(pos+1,level+1,nums,path-nums[pos]);
  68.         }
  69.     }
  70.  
  71. };

21. 组合总和

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  1. class Solution {
  2. public:
  3. //第一个位置的数选一个两个三个依次往下递归
  4. //第二个数也是如此
  5. //恢复现场时候要把本层push_back进去的所有数据全部pop_back出去
  6.     vector<vector<int>> ret;
  7.     vector<int> path;
  8.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
  9.     {
  10.         dfs(candidates,0,target,0);
  11.         return ret;
  12.     }
  13.  
  14.     void dfs(vector<int>& candidates,int sum,const int& target,int pos)//sum为递归到本层的和
  15.     {
  16.         if(sum>=target)
  17.         {
  18.             if(sum==target)ret.push_back(path);
  19.             return;
  20.         }
  21.         if(pos==candidates.size())//防止越界访问而导致的内存问题
  22.         {
  23.             return;
  24.         }
  25.  
  26.         for(int i=0;sum+i*candidates[pos]<=target;i++)
  27.         {
  28.             //cout<<candidates[pos];
  29.             if(i) path.push_back(candidates[pos]); //注意这个if(i)
  30.             dfs(candidates,sum+i*candidates[pos],target,pos+1);
  31.         }
  32.         //cout<<endl;
  33.  
  34.         for(int i=1;sum+i*candidates[pos]<=target;i++)//上面的if(i)决定了这里从i==1开始删除
  35.         {
  36.             //cout<<candidates[pos];
  37.             path.pop_back();
  38.         }
  39.         //cout<<endl;
  40.  
  41.     }
  42.  
  43. };

此题还有另一种解法

就是每一个位置的数对其所有可能进行枚举

22. 字母大小写全排列

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  1. class Solution {
  2. public:
  3.     string path;
  4.     vector<string> ret;
  5.     vector<string> letterCasePermutation(string s) 
  6.     {
  7.         dfs(0,s);
  8.         return ret;
  9.     }
  10.  
  11.     void dfs(int pos,const string& s)
  12.     {
  13.         if(pos==s.size())
  14.         {
  15.             ret.push_back(path);
  16.             return;
  17.         }
  18.         char tmp=s[pos];
  19.  
  20.         path.push_back(tmp);
  21.         dfs(pos+1,s);
  22.         path.pop_back();
  23.         if(tmp<'0'||tmp>'9')//如果是字符
  24.         {
  25.             change(tmp);
  26.             path.push_back(tmp);
  27.             dfs(pos+1,s);
  28.             path.pop_back();
  29.  
  30.         }
  31.  
  32.     }
  33.  
  34.     void change(char& ch)
  35.     {
  36.         if(ch>='a'&&ch<='z')//这里的-= +=l弄错了
  37.         {
  38.             ch-=32;
  39.         }
  40.         else if(ch>='A'&&ch<='Z')
  41.         {
  42.             ch+=32;
  43.         }
  44.     }
  45. };

23. 优美的排列

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  1. class Solution {
  2. public:
  3.     vector<int> path;
  4.     int ret;
  5.     vector<bool> check;
  6.     int max=0;
  7.     int countArrangement(int n) {
  8.         check.resize(n+1,false);
  9.         path.resize(n+1);
  10.         max=n;
  11.         dfs(1);
  12.         return ret;
  13.     }
  14.     void dfs(int pos)
  15.     {
  16.         if(max==pos)
  17.         {
  18.             ++ret;
  19.             return;
  20.         }
  21.  
  22.         for(int i=1;i<max+1;i++)
  23.         {
  24.             if(check[i]==true)
  25.             {
  26.                 continue;
  27.             }
  28.  
  29.             if(pos%i==0||i%pos==0)
  30.             {
  31.                 check[i]=true;
  32.                 path.push_back(i);
  33.                 dfs(pos+1);
  34.                 path.pop_back();
  35.                 check[i]=false;
  36.             }
  37.         }
  38.     }
  39. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/434276
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号