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

递归、dfs、回溯、剪枝，一针见血的_递归 剪枝

作者：我家自动化 | 2024-04-16 12:56:17

赞

踩

递归 剪枝

一、框架：

回溯搜索的遍历过程：回溯法⼀般是在集合中递归搜索，集合的⼤⼩构成了树的宽度，递归的

深度构成的树的深度。

for循环就是遍历集合区间，可以理解⼀个节点有多少个孩⼦，这个for循环就执⾏多少次。

backtracking这⾥⾃⼰调⽤⾃⼰，实现递归。

⼤家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，

这样就把这棵树全遍历完了，⼀般来说，搜索叶⼦节点就是找的其中⼀个结果了。

分析完过程，回溯算法模板框架如下：

二、题目举例

1、组合问题

第77题. 组合

题⽬链接：https://leetcode-cn.com/problems/combinations/

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

⽰例:

输⼊: n = 4, k = 2

输出:

[

[2,4],

[3,4],

[2,3],

[1,2],

[1,3],

[1,4],

]

思路

也可以直接看我的B站视频：带你学透回溯算法-组合问题（对应⼒扣题⽬：77.组合）

本题这是回溯法的经典题⽬。

直接的解法当然是使⽤for循环，例如⽰例中k为2，很容易想到 ⽤两个for循环，这样就可以

输出 和⽰例中⼀样的结果。代码如下：

  1. int n = 4;
  2. for (int i = 1; i <= n; i++) {
  3.  for (int j = i + 1; j <= n; j++) {
  4.  cout << i << " " << j << endl;
  5.  }
  6. }

输⼊：n = 100, k = 3

那么就三层for循环，代码如下：

  1. int n = 100;
  2. for (int i = 1; i <= n; i++) {
  3.  for (int j = i + 1; j <= n; j++) {
  4.  for (int u = j + 1; u <= n; n++) {
  5.  cout << i << " " << j << " " << u << endl;
  6.  }
  7.  }
  8. }

如果n为100，k为50呢，那就50层for循环，此时就会发现虽然想暴⼒搜索，但是⽤for循环嵌套连暴⼒都写不出来！

咋整？

回溯搜索法来了，虽然回溯法也是暴⼒，但⾄少能写出来，不像for循环嵌套k层让⼈绝望。

那么回溯法怎么暴⼒搜呢？

上⾯我们说了要解决 n为100，k为50的情况，暴⼒写法需要嵌套50层for循环，那么回溯法就⽤递归来解决嵌套层数的问题。

递归来做层叠嵌套（可以理解是开k层for循环），每⼀次的递归中嵌套⼀个for循环，那么

递归就可以⽤于解决多层嵌套循环的问题了。此时递归的层数⼤家应该知道了，例如：n为100，k为50的情况下，就是递归50层。

如果脑洞模拟回溯搜索的过程，绝对可以让⼈窒息，所以需要抽象图形结构来进⼀步理解。

回溯法解决的问题都可以抽象为树形结构（N叉树），⽤树形结构来理解回溯就容易多了。

那么我把组合问题抽象为如下树形结构：

可以看出这个棵树，⼀开始集合是 1，2，3，4， 从左向右取数，取过的数，不在重复取。

第⼀次取1，集合变为2，3，4 ，因为k为2，我们只需要再取⼀个数就可以了，分别取2，

3，4，得到集合[1,2] [1,3] [1,4]，以此类推。

每次从集合中选取元素，可选择的范围随着选择的进⾏⽽收缩，调整可选择的范围。

图中可以发现n相当于树的宽度，k相当于树的深度。

总结：递归的第1层：选数都是从1开始选；递归的第2层：选数都是从2开始选，k为2的时候选两个数，所以树的高度为两层，因此k为多少，树的高度就为多少。

重点来了，那么如何在这个树上遍历，然后收集到我们要的结果集呢？

图中每次搜索到了叶⼦节点，我们就找到了⼀个结果。

相当于只需要把达到叶⼦节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

重点又来了，如何用代码实现呢？

思路：

函数⾥⼀定有两个参数，既然是集合n⾥⾯取k的数，那么n和k是两个int型的参数。

然后还需要⼀个参数，为int型变量startIndex，这个参数⽤来记录本层递归的中，集合从哪

⾥开始遍历（集合就是[1,...,n] ）。

为什么要有这个startIndex呢？

每次从集合中选取元素，可选择的范围随着选择的进⾏⽽收缩，调整可选择的范围，就是要

靠startIndex。

从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下⼀层递归，就要在[2,3,4]中取数

了，那么下⼀层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。

所以需要startIndex来记录下⼀层递归，搜索的起始位置。

步骤：

（1）回溯函数终⽌条件

什么时候到达所谓的叶⼦节点了呢？

path这个数组的⼤⼩如果达到k，说明我们找到了⼀个⼦集⼤⼩为k的组合了，在图中path

存的就是根节点到叶⼦节点的路径。

如图红⾊部分：

  1. if(path.size() == k)
  2. {
  3.      for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  4.      out.println();
  5.      out.flush();
  6.      return;
  7. }

（2）单层搜索的过程

回溯法的搜索过程就是⼀个树型结构的遍历过程，在如下图中，可以看出for循环⽤来横向

遍历，递归的过程是纵向遍历。

如此我们才遍历完图中的这棵树。

for循环每次从startIndex开始遍历，然后⽤path保存取到的节点i。

  1. for(int i = startIndex ; i <= n ; i ++)
  2. {
  3.      // 变长数组的add是每一次都是从变长数组的最后添加一个元素
  4.      path.add(i);
  5.      // 不用打标记的原因就是：只要选了一个，i ++，选的数字都是递增的，序列是递增的
  6.      dfs(n, k, i + 1);
  7.      // 恢复现场，弹出刚才添加到路径的数
  8.      path.remove(path.size() - 1);
  9. }

可以看出dfs（递归函数）通过不断调⽤⾃⼰⼀直往深处遍历，总会遇到叶⼦节

点，遇到了叶⼦节点就要返回。

完整的dfs代码：

  1. static void dfs(int n,int k,int startIndex)
  2. {
  3.     if(path.size() == k)
  4.     {
  5.         for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  6.         out.println();
  7.         out.flush();
  8.         return;
  9.     }
  10.         
  11.     for(int i = startIndex ; i <= n ; i ++)
  12.     {
  13.          // 变长数组的add是每一次都是从变长数组的最后添加一个元素
  14.          path.add(i);
  15.          // 不用打标记的原因就是：只要选了一个，i ++，选的数字都是递增的，序列是递增的
  16.          dfs(n, k, i + 1);
  17.          // 恢复现场，弹出刚才添加到路径的数
  18.          path.remove(path.size() - 1);
  19.      }
  20. }

实操代码：

  1. package hly;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.BufferedWriter;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.nio.file.attribute.AclEntryFlag;
  11. import java.security.AlgorithmConstraints;
  12. import java.text.DateFormatSymbols;
  13. import java.util.ArrayList;
  14. import java.util.List;
  15. import java.util.StringTokenizer;
  16. import java.util.Vector;
  17.  
  18. class in 
  19. {
  20.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  21.     static StringTokenizer tokenizer = new StringTokenizer("");
  22.     
  23.     static String nextLine() throws IOException   { return reader.readLine(); }
  24.     
  25.     static String next() throws IOException 
  26.     {
  27.         while (!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  28.         return tokenizer.nextToken();
  29.     }
  30.  
  31.     static int nextInt() throws IOException  { return Integer.parseInt(next()); }
  32.  
  33.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  34.     
  35.     static long nextLong() throws IOException  { return Long.parseLong(next());}
  36.     
  37.     static BigInteger nextBigInteger() throws IOException 
  38.     { 
  39.         BigInteger d = new BigInteger(in.nextLine());
  40.         return d;
  41.     }
  42. }
  43.  
  44. public class 组合问题 
  45. {
  46.     static int N = 100;
  47.     static int n;
  48.     static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); 
  49.     //动态数组存路径可太行了
  50.     static List<Integer> path = new ArrayList<>();
  51.     
  52.      static void dfs(int n,int k,int startIndex)
  53.     {
  54.         if(path.size() == k)
  55.         {
  56.             for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  57.             out.println();
  58.             out.flush();
  59.             return;
  60.         }
  61.         
  62.         for(int i = startIndex ; i <= n ; i ++)
  63.         {
  64.             // 变长数组的add是每一次都是从变长数组的最后添加一个元素
  65.             path.add(i);
  66.             // 不用打标记的原因就是：只要选了一个，i ++，选的数字都是递增的，序列是递增的
  67.             dfs(n, k, i + 1);
  68.             // 恢复现场，弹出刚才添加到路径的数
  69.             path.remove(path.size() - 1);
  70.         }
  71.     }
  72.     
  73.     public static void main(String[] args) throws IOException 
  74.     {
  75.          int n = in.nextInt();
  76.          int k = in.nextInt();
  77.          
  78.          // 
  79.          dfs(n,k,1);
  80.          out.flush();
  81.     }
  82. }

剪枝优化：

来举⼀个例⼦，n = 4，k = 4的话，那么第⼀层for循环的时候，从元素2开始的遍历都没有

意义了。 在第⼆层for循环，从元素3开始的遍历都没有意义了。

这么说有点抽象，如图所⽰：

图中每⼀个节点（图中为矩形），就代表本层的⼀个for循环，那么每⼀层的for循环从第⼆

个数开始遍历的话，都没有意义，都是⽆效遍历。

所以，可以剪枝的地⽅就在递归中每⼀层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不⾜ 我们需要的元素个数了，那么就没有

必要搜索了。

原来的for循环代码：

for(int i = startIndex ; i <= n ; i ++)

接下来看⼀下优化过程如下：

1. 已经选择的元素个数：path.size();

2. 还需要的元素个数为: k - path.size();

3. 在集合n中⾄多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是⼀个左闭的集合。

举个例⼦，n = 4，k = 3， ⽬前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - (3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

这⾥⼤家想不懂的话，建议也举⼀个例⼦，就知道是不是要+1了。

所以优化之后的for循环是：

for(int i = startIndex ; i <=  n - (k - path.size()) + 1 ; i ++)

实操：

  1. package hly;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.BufferedWriter;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.nio.file.attribute.AclEntryFlag;
  11. import java.security.AlgorithmConstraints;
  12. import java.text.DateFormatSymbols;
  13. import java.util.ArrayList;
  14. import java.util.List;
  15. import java.util.StringTokenizer;
  16. import java.util.Vector;
  17.  
  18. class in 
  19. {
  20.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  21.     static StringTokenizer tokenizer = new StringTokenizer("");
  22.     
  23.     static String nextLine() throws IOException   { return reader.readLine(); }
  24.     
  25.     static String next() throws IOException 
  26.     {
  27.         while (!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  28.         return tokenizer.nextToken();
  29.     }
  30.  
  31.     static int nextInt() throws IOException  { return Integer.parseInt(next()); }
  32.  
  33.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  34.     
  35.     static long nextLong() throws IOException  { return Long.parseLong(next());}
  36.     
  37.     static BigInteger nextBigInteger() throws IOException 
  38.     { 
  39.         BigInteger d = new BigInteger(in.nextLine());
  40.         return d;
  41.     }
  42. }
  43.  
  44. public class 组合问题 
  45. {
  46.     static int N = 100;
  47.     static int n;
  48.     static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); 
  49.     //动态数组存路径可太行了
  50.     static List<Integer> path = new ArrayList<>();
  51.     
  52.      static void dfs(int n,int k,int startIndex)
  53.     {
  54.         if(path.size() == k)
  55.         {
  56.             for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  57.             out.println();
  58.             out.flush();
  59.             return;
  60.         }
  61.         
  62.         for(int i = startIndex ; i <=  n - (k - path.size()) + 1 ; i ++)
  63.         {
  64.             // 变长数组的add是每一次都是从变长数组的最后添加一个元素
  65.             path.add(i);
  66.             // 不用打标记的原因就是：只要选了一个，i ++，选的数字都是递增的，序列是递增的
  67.             dfs(n, k, i + 1);
  68.             // 恢复现场，弹出刚才添加到路径的数
  69.             path.remove(path.size() - 1);
  70.         }
  71.     }
  72.     
  73.     public static void main(String[] args) throws IOException 
  74.     {
  75.          int n = in.nextInt();
  76.          int k = in.nextInt();
  77.          
  78.          // 
  79.          dfs(n,k,1);
  80.          out.flush();
  81.     }
  82. }

二、组合总和（⼀）

问题：找出在[1,2,3,...，n]这个集合中找到和为target的k个数的组合。

相对于回溯算法：求组合问题！，⽆⾮就是多了⼀个限制，本题是要找到和为target的k个数的组合，想到这⼀点了，做过77. 组合之后，本题是简单⼀些了。

本题k相当于了树的深度，9（因为整个集合就是9个数）就是树的宽度。例如 k = 2，n = 4的话，就是在集合[1,2,3,...，n]中求 k（个数） = 2, target（和） = 4的组合。

选取过程如图：

简简单单，只有和的约束，和上题几乎相同，直接上代码

  1. package hly;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.BufferedWriter;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.nio.file.attribute.AclEntryFlag;
  11. import java.security.AlgorithmConstraints;
  12. import java.text.DateFormatSymbols;
  13. import java.util.ArrayList;
  14. import java.util.List;
  15. import java.util.StringTokenizer;
  16. import java.util.Vector;
  17.  
  18. class in 
  19. {
  20.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  21.     static StringTokenizer tokenizer = new StringTokenizer("");
  22.     
  23.     static String nextLine() throws IOException   { return reader.readLine(); }
  24.     
  25.     static String next() throws IOException 
  26.     {
  27.         while (!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  28.         return tokenizer.nextToken();
  29.     }
  30.  
  31.     static int nextInt() throws IOException  { return Integer.parseInt(next()); }
  32.  
  33.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  34.     
  35.     static long nextLong() throws IOException  { return Long.parseLong(next());}
  36.     
  37.     static BigInteger nextBigInteger() throws IOException 
  38.     { 
  39.         BigInteger d = new BigInteger(in.nextLine());
  40.         return d;
  41.     }
  42. }
  43.  
  44. public class 组合问题 
  45. {
  46.     static int N = 100;
  47.     static int n;
  48.     static int k;
  49.     static int target;
  50.     static int sum = 0;
  51.     static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); 
  52.     //动态数组存路径可太行了
  53.     static List<Integer> path = new ArrayList<>();
  54.     
  55.      static void dfs(int n,int k,int target, int startIndex)
  56.     {
  57.         if(path.size() == k)
  58.         {
  59.             if(sum == target)
  60.             {
  61.                 for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  62.                 out.println();
  63.                 out.flush();
  64.                 return;
  65.             }
  66.             return;
  67.         }
  68.         
  69.         for(int i = startIndex ; i <=  n - (k - path.size()) + 1 ; i ++)
  70.         {
  71.             // 变长数组的add是每一次都是从变长数组的最后添加一个元素
  72.             path.add(i);        
  73.             sum += i;
  74.             // 不用打标记的原因就是：只要选了一个，i ++，选的数字都是递增的，序列是递增的
  75.             dfs(n, k,target, i + 1);
  76.             // 恢复现场，弹出刚才添加到路径的数
  77.             path.remove(path.size() - 1);
  78.             sum -= i;
  79.         }
  80.     }
  81.     
  82.     public static void main(String[] args) throws IOException 
  83.     {
  84.          n = in.nextInt();
  85.          k = in.nextInt();
  86.          target = in.nextInt();
  87.          
  88.          // 
  89.          dfs(n,k,target,1);
  90.          out.flush();
  91.     }
  92. }

剪汁儿来辣！

观察图得，已选元素总和如果已经⼤于n（图中数值为4）了，但是还不够k个，那么往后遍历就没有意义了，直接剪掉。剪枝的地⽅⼀定是在递归终⽌的地⽅剪，剪枝代码如下：

if(sum > target)  return;

实操：

  1. package hly;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.BufferedWriter;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.nio.file.attribute.AclEntryFlag;
  11. import java.security.AlgorithmConstraints;
  12. import java.text.DateFormatSymbols;
  13. import java.util.ArrayList;
  14. import java.util.List;
  15. import java.util.StringTokenizer;
  16. import java.util.Vector;
  17.  
  18. class in 
  19. {
  20.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  21.     static StringTokenizer tokenizer = new StringTokenizer("");
  22.     
  23.     static String nextLine() throws IOException   { return reader.readLine(); }
  24.     
  25.     static String next() throws IOException 
  26.     {
  27.         while (!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  28.         return tokenizer.nextToken();
  29.     }
  30.  
  31.     static int nextInt() throws IOException  { return Integer.parseInt(next()); }
  32.  
  33.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  34.     
  35.     static long nextLong() throws IOException  { return Long.parseLong(next());}
  36.     
  37.     static BigInteger nextBigInteger() throws IOException 
  38.     { 
  39.         BigInteger d = new BigInteger(in.nextLine());
  40.         return d;
  41.     }
  42. }
  43.  
  44. public class 组合问题 
  45. {
  46.     static int N = 100;
  47.     static int n;
  48.     static int k;
  49.     static int target;
  50.     static int sum = 0;
  51.     static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); 
  52.     //动态数组存路径可太行了
  53.     static List<Integer> path = new ArrayList<>();
  54.     
  55.      static void dfs(int n,int k,int target, int startIndex)
  56.     {
  57.          if(sum > target)  return;
  58.          
  59.         if(path.size() == k)
  60.         {
  61.             if(sum == target)
  62.             {
  63.                 for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  64.                 out.println();
  65.                 out.flush();
  66.                 return;
  67.             }
  68.             return;
  69.         }
  70.         
  71.         for(int i = startIndex ; i <=  n - (k - path.size()) + 1 ; i ++)
  72.         {
  73.             // 变长数组的add是每一次都是从变长数组的最后添加一个元素
  74.             path.add(i);        
  75.             sum += i;
  76.             // 不用打标记的原因就是：只要选了一个，i ++，选的数字都是递增的，序列是递增的
  77.             dfs(n, k,target, i + 1);
  78.             // 恢复现场，弹出刚才添加到路径的数
  79.             path.remove(path.size() - 1);
  80.             sum -= i;
  81.         }
  82.     }
  83.     
  84.     public static void main(String[] args) throws IOException 
  85.     {
  86.          n = in.nextInt();
  87.          k = in.nextInt();
  88.          target = in.nextInt();
  89.          
  90.          // 
  91.          dfs(n,k,target,1);
  92.          out.flush();
  93.     }
  94. }

变种1：（好像更简单了）

问题：找出在[1,2,3，...，n]这个集合中找到和为staget的组合。（组合的元素没有个数限制、组合内元素不能重复）

代码：

  1. package hly;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.BufferedWriter;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.nio.file.attribute.AclEntryFlag;
  11. import java.security.AlgorithmConstraints;
  12. import java.text.DateFormatSymbols;
  13. import java.util.ArrayList;
  14. import java.util.List;
  15. import java.util.StringTokenizer;
  16. import java.util.Vector;
  17.  
  18. class in 
  19. {
  20.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  21.     static StringTokenizer tokenizer = new StringTokenizer("");
  22.     
  23.     static String nextLine() throws IOException   { return reader.readLine(); }
  24.     
  25.     static String next() throws IOException 
  26.     {
  27.         while (!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  28.         return tokenizer.nextToken();
  29.     }
  30.  
  31.     static int nextInt() throws IOException  { return Integer.parseInt(next()); }
  32.  
  33.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  34.     
  35.     static long nextLong() throws IOException  { return Long.parseLong(next());}
  36.     
  37.     static BigInteger nextBigInteger() throws IOException 
  38.     { 
  39.         BigInteger d = new BigInteger(in.nextLine());
  40.         return d;
  41.     }
  42. }
  43.  
  44. public class 组合问题 
  45. {
  46.     static int N = 100;
  47.     static int n;
  48.     static int k;
  49.     static int target;
  50.     static int sum = 0;
  51.     static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); 
  52.     //动态数组存路径可太行了
  53.     static List<Integer> path = new ArrayList<>();
  54.     
  55.      static void dfs(int n,int target, int startIndex)
  56.     {
  57.          if(sum > target)  return;
  58.          
  59.         if(sum == target)
  60.         {
  61.             for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  62.             out.println();
  63.             out.flush();
  64.             return;
  65.         }
  66.         
  67.         
  68.         for(int i = startIndex ; i <=  n ; i ++)
  69.         {
  70.             // 变长数组的add是每一次都是从变长数组的最后添加一个元素
  71.             path.add(i);        
  72.             sum += i;
  73.             // 不用打标记的原因就是：只要选了一个，i ++，选的数字都是递增的，序列是递增的
  74.             dfs(n,target, i + 1);
  75.             // 恢复现场，弹出刚才添加到路径的数
  76.             path.remove(path.size() - 1);
  77.             sum -= i;
  78.         }
  79.     }
  80.     
  81.     public static void main(String[] args) throws IOException 
  82.     {
  83.          n = in.nextInt();
  84.          target = in.nextInt();
  85.          
  86.          dfs(n,target,1);
  87.          out.flush();
  88.     }
  89. }

变种2：

问题：找出在[1,2,3，...，n]这个集合中找到和为target的组合。（组合的元素没有个数限制、组合内元素可以重复）

相较于上边的变种1：dfs(n,target, i + 1);改为dfs(n,target, i );其余代码相同
真是妙哎~

代码：

  1. package hly;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.BufferedWriter;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.nio.file.attribute.AclEntryFlag;
  11. import java.security.AlgorithmConstraints;
  12. import java.text.DateFormatSymbols;
  13. import java.util.ArrayList;
  14. import java.util.List;
  15. import java.util.StringTokenizer;
  16. import java.util.Vector;
  17.  
  18. class in 
  19. {
  20.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  21.     static StringTokenizer tokenizer = new StringTokenizer("");
  22.     
  23.     static String nextLine() throws IOException   { return reader.readLine(); }
  24.     
  25.     static String next() throws IOException 
  26.     {
  27.         while (!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  28.         return tokenizer.nextToken();
  29.     }
  30.  
  31.     static int nextInt() throws IOException  { return Integer.parseInt(next()); }
  32.  
  33.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  34.     
  35.     static long nextLong() throws IOException  { return Long.parseLong(next());}
  36.     
  37.     static BigInteger nextBigInteger() throws IOException 
  38.     { 
  39.         BigInteger d = new BigInteger(in.nextLine());
  40.         return d;
  41.     }
  42. }
  43.  
  44. public class 组合问题 
  45. {
  46.     static int N = 100;
  47.     static int n;
  48.     static int k;
  49.     static int target;
  50.     static int sum = 0;
  51.     static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); 
  52.     //动态数组存路径可太行了
  53.     static List<Integer> path = new ArrayList<>();
  54.     
  55.      static void dfs(int n,int target, int startIndex)
  56.     {
  57.          if(sum > target)  return;
  58.          
  59.         if(sum == target)
  60.         {
  61.             for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  62.             out.println();
  63.             out.flush();
  64.             return;
  65.         }
  66.         
  67.         
  68.         for(int i = startIndex ; i <=  n ; i ++)
  69.         {
  70.             // 变长数组的add是每一次都是从变长数组的最后添加一个元素
  71.             path.add(i);        
  72.             sum += i;
  73.             // 不用打标记的原因就是：只要选了一个，i ++，选的数字都是递增的，序列是递增的
  74.             dfs(n,target, i);
  75.             // 恢复现场，弹出刚才添加到路径的数
  76.             path.remove(path.size() - 1);
  77.             sum -= i;
  78.         }
  79.     }
  80.     
  81.     public static void main(String[] args) throws IOException 
  82.     {
  83.          n = in.nextInt();
  84.          target = in.nextInt();
  85.          
  86.          dfs(n,target,1);
  87.          out.flush();
  88.     }
  89. }

变种3：

问题：找出在长度为n的数组a（无重复元素）中找到和为target的组合。（组合的元素没有个数限制、组合内元素可以重复、组合间允许重复）

⽰例 1：

输⼊：n = 4，candidates = [2,3,6,7], target = 7,

所求解集为：

[

[7],

[2,2,3]

]

⽰例 2：

输⼊：n = 3，candidates = [2,3,5], target = 8,

所求解集为：

[

[2,2,2,2],

[2,3,3],

[3,5]

]

注意图中叶⼦节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归

没有层数的限制，只要选取的元素总和超过target，就返回！

⽽在第一个问题中都可以知道要递归K层，因为要取k个元素的组合。

本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要

startIndex呢？

我举过例⼦，如果是⼀个集合来求组合的话，就需要startIndex，例如：回溯算法：求组合

问题！，回溯算法：求组合总和！。

如果是多个集合取组合，各个集合之间相互不影响，那么就不⽤startIndex，例如：回溯算

法：电话号码的字母组合

注意以上我只是说求组合的情况，如果是排列问题，又是另⼀套分析的套路，后⾯我再讲解

排列的时候就重点介绍。

  1. package hly;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.BufferedWriter;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.nio.file.attribute.AclEntryFlag;
  11. import java.security.AlgorithmConstraints;
  12. import java.text.DateFormatSymbols;
  13. import java.util.ArrayList;
  14. import java.util.List;
  15. import java.util.StringTokenizer;
  16. import java.util.Vector;
  17.  
  18. class in 
  19. {
  20.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  21.     static StringTokenizer tokenizer = new StringTokenizer("");
  22.     
  23.     static String nextLine() throws IOException   { return reader.readLine(); }
  24.     
  25.     static String next() throws IOException 
  26.     {
  27.         while (!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  28.         return tokenizer.nextToken();
  29.     }
  30.  
  31.     static int nextInt() throws IOException  { return Integer.parseInt(next()); }
  32.  
  33.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  34.     
  35.     static long nextLong() throws IOException  { return Long.parseLong(next());}
  36.     
  37.     static BigInteger nextBigInteger() throws IOException 
  38.     { 
  39.         BigInteger d = new BigInteger(in.nextLine());
  40.         return d;
  41.     }
  42. }
  43.  
  44. public class 组合问题 
  45. {
  46.     static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); 
  47.     
  48.     static int N = 100;
  49.     static int n;
  50.     static int k;
  51.     static int target;
  52.     static int sum = 0;
  53.     static int a[] = new int[N];
  54.     
  55.     //动态数组存路径可太行了
  56.     static List<Integer> path = new ArrayList<>();
  57.     
  58.      static void dfs(int target, int startIndex)
  59.     {
  60.          if(sum > target)  return;
  61.          
  62.         if(sum == target)
  63.         {
  64.             for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  65.             out.println();
  66.             out.flush();
  67.             return;
  68.         }
  69.         
  70.         
  71.         for(int i = startIndex ; i < n ; i ++)
  72.         {
  73.             path.add(a[i]);        
  74.             sum += a[i];
  75.             
  76.             dfs(target, i);
  77.            
  78.             path.remove(path.size() - 1);
  79.             sum -= a[i];
  80.         }
  81.     }
  82.     
  83.     public static void main(String[] args) throws IOException 
  84.     {
  85.          n = in.nextInt();
  86.          for(int i = 0 ; i < n ; i ++)  a[i] = in.nextInt();
  87.          target = in.nextInt();
  88.          
  89.          dfs(target,0);
  90.          out.flush();
  91.     }
  92. }

剪枝优化：

在这个树形结构中：

对于sum已经⼤于target的情况，其实是依然进⼊

了下⼀层递归，只是下⼀层递归结束判断的时候，会判断sum > target的话就返回。

其实如果已经知道下⼀层的sum会⼤于target，就没有必要进⼊下⼀层递归了。

那么可以在for循环的搜索范围上做做⽂章了。

对总集合排序之后，如果下⼀层的sum（就是本层的 sum + candidates[i]）已经⼤于

target，就可以结束本轮for循环的遍历。

如图：

for循环剪枝代码如下：

for(int i = startIndex ; i < n && sum + a[i] <= target ; i ++)

实操：

  1. package hly;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.BufferedWriter;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.nio.file.attribute.AclEntryFlag;
  11. import java.security.AlgorithmConstraints;
  12. import java.text.DateFormatSymbols;
  13. import java.util.ArrayList;
  14. import java.util.Arrays;
  15. import java.util.List;
  16. import java.util.StringTokenizer;
  17. import java.util.Vector;
  18.  
  19. class in 
  20. {
  21.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  22.     static StringTokenizer tokenizer = new StringTokenizer("");
  23.     
  24.     static String nextLine() throws IOException   { return reader.readLine(); }
  25.     
  26.     static String next() throws IOException 
  27.     {
  28.         while (!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  29.         return tokenizer.nextToken();
  30.     }
  31.  
  32.     static int nextInt() throws IOException  { return Integer.parseInt(next()); }
  33.  
  34.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  35.     
  36.     static long nextLong() throws IOException  { return Long.parseLong(next());}
  37.     
  38.     static BigInteger nextBigInteger() throws IOException 
  39.     { 
  40.         BigInteger d = new BigInteger(in.nextLine());
  41.         return d;
  42.     }
  43. }
  44.  
  45. public class 组合问题 
  46. {
  47.     static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); 
  48.     
  49.     static int N = 100;
  50.     static int n;
  51.     static int k;
  52.     static int target;
  53.     static int sum = 0;
  54.     static int a[] = new int[N];
  55.     
  56.     //动态数组存路径可太行了
  57.     static List<Integer> path = new ArrayList<>();
  58.     
  59.      static void dfs(int target, int startIndex)
  60.     {    
  61.         if(sum > target)  return;
  62.  
  63.         if(sum == target)
  64.         {
  65.             for(int i = 0 ; i < path.size(); i ++)  out.printf("%d",path.get(i));
  66.             out.println();
  67.             out.flush();
  68.             return;
  69.         }
  70.         
  71.         // 如果 sum + a[i] > target 就终⽌遍历
  72.         for(int i = startIndex ; i < n && sum + a[i] <= target ; i ++)
  73.         {
  74.             path.add(a[i]);        
  75.             sum += a[i];
  76.             
  77.             dfs(target, i);
  78.             
  79.             path.remove(path.size() - 1);
  80.             sum -= a[i];
  81.         }
  82.     }
  83.     
  84.     public static void main(String[] args) throws IOException 
  85.     {
  86.          n = in.nextInt();
  87.          for(int i = 0 ; i < n ; i ++)  a[i] = in.nextInt();
  88.          target = in.nextInt();
  89.          
  90.          Arrays.sort(a,0,n);
  91.          dfs(target,0);
  92.          out.flush();
  93.     }
  94. }

实战：题目1(求最长路)

题意：给出一个图，找出一条路，经过最多的边，可以经过重复的点但是不能经过重复的边。

题目给出了全部的边，不能自己加边，求最长路

节点编号从0到n-1。边是无向的。

找出在给定无向图中的最长路径

节点的度数为3或更少。网络不需要连接。

节点可多次访问，边只能访问一次

思路：数据量这么小，暴搜吧

AC代码：

  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.io.OutputStreamWriter;
  6. import java.io.PrintWriter;
  7. import java.math.BigInteger;
  8. import java.util.*;
  9.  
  10.  
  11.  
  12. public class Main
  13. {
  14.     static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  15.     static int N = (int)100;
  16.     static boolean g[][] = new boolean[N][N]; // 记录点到点是否连通，连通即为true
  17.     static boolean visited[][] = new boolean[N][N]; // 记录每条边有没有访问过
  18.  
  19.     static int n,m; // 地图信息
  20.     static int res;  // 存最长路径
  21.  
  22.     static void dfs(int a,int len) // 找a点能到其他点的最长路径，每条边的权重为1
  23.     {
  24.         res = Math.max(res,len);  // 没进入dfs函数，就更新最长路径
  25.  
  26.         // 枚举该点到其他点的边
  27.         for(int i = 0 ; i < n ; i ++)
  28.         {
  29.             if(!g[a][i]|| visited[a][i])  continue;  // 两点之间没有边或者已经这个边已经被访问过
  30.             visited[a][i] = visited[i][a] = true;
  31.             dfs(i,len + 1);
  32.             visited[a][i] = visited[i][a] = false;
  33.         }
  34.     }
  35.  
  36.     public static void main(String[] args ) throws IOException
  37.     {
  38.         while (true)
  39.         {
  40.             n = rd.nextInt();
  41.             m = rd.nextInt();
  42.             if(n == 0 || m == 0)  return;
  43.  
  44.             res = 0; // 初始化答案
  45.             for(int i = 0 ; i < N  ; i ++)  Arrays.fill(g[i],false); // 初始化图中点与点是否连通的关系
  46.  
  47.             for(int i = 0 ; i < m ; i ++)
  48.             {
  49.                 int a = rd.nextInt(),b = rd.nextInt();
  50.                 g[a][b] = g[b][a] = true; // 两个点之间是有边的
  51.             }
  52.  
  53.             int len = 0;
  54.             for(int i = 0 ; i < n ; i ++)
  55.             {
  56.                 for(int j = 0 ; j < N  ; j ++)  Arrays.fill(visited[j],false);  // 寻找每个点的最长路之前，需要重置visited数组
  57.                 dfs(i,0);
  58.             }
  59.             pw.println(res);
  60.             pw.flush();
  61.         }
  62.     }
  63. }
  64.  
  65. class rd
  66. {
  67.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  68.     static StringTokenizer tokenizer = new StringTokenizer("");
  69.  
  70.     static String nextLine() throws IOException  { return reader.readLine(); }
  71.  
  72.     static String next() throws IOException
  73.     {
  74.         while (!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  75.         return tokenizer.nextToken();
  76.     }
  77.  
  78.     static int nextInt() throws IOException  { return Integer.parseInt(next()); }
  79.  
  80.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  81.  
  82.     static long nextLong() throws IOException  { return Long.parseLong(next());}
  83.  
  84.     static BigInteger nextBigInteger() throws IOException
  85.     {
  86.         BigInteger d = new BigInteger(rd.nextLine());
  87.         return d;
  88.     }
  89. }
  90.  
  91. class PII
  92. {
  93.     int x,y;
  94.     public PII(int x ,int y)
  95.     {
  96.         this.x = x;
  97.         this.y = y;
  98.     }
  99. }

题目：

题目描述

任何一个大于 1 的自然数 n，总可以拆分成若干个小于 n 的自然数之和。现在给你一个自然数 n，要求你求出 n 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

输入格式

输入：待拆分的自然数 n。

输出格式

输出：若干数的加法式子。

输入输出样例

输入 #1复制

7

输出 #1复制

1+1+1+1+1+1+1

1+1+1+1+1+2

1+1+1+1+3

1+1+1+2+2

1+1+1+4

1+1+2+3

1+1+5

1+2+2+2

1+2+4

1+3+3

1+6

2+2+3

2+5

3+4

代码：

  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.text.ParseException;
  4. import java.text.SimpleDateFormat;
  5. import java.util.*;
  6. import java.util.stream.Collectors;
  7.  
  8. public class Main
  9. {
  10.     static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  11.     static math math_bag = new math();
  12.     static int N = (int)1e6 + 10;
  13.     static int d[] = new int[N];
  14.     static List<Integer> path = new ArrayList<>();
  15.  
  16.     static int n;
  17.     static int sum;
  18.  
  19.     // 2次幂的预处理
  20.     static void init_2_pow()
  21.     {
  22.         d[0] = 1;
  23.         for(int i = 1 ; i <= 31 ; i ++)  d[i] = d[i - 1]*2;
  24.     }
  25.  
  26.     static void dfs(int StartIndex) // 从StartIndex开始选，总和为sum
  27.     {
  28.          if(sum > n)  return;
  29.          if(sum == n)
  30.          {
  31.              pw.print(path.get(0));
  32.              for(int i = 1 ; i < path.size() ; i ++)  pw.print("+" + path.get(i));
  33.              pw.println();
  34.              return;
  35.          }
  36.  
  37.          for(int i = StartIndex ; i + sum <= n && i <= n ; i ++)
  38.          {
  39.              path.add(i);
  40.              sum += i;
  41.              dfs(i);
  42.              path.remove(path.size() - 1);
  43.              sum -= i;
  44.          }
  45.     }
  46.  
  47.     public static void main(String[] args ) throws IOException, ParseException
  48.     {
  49.         n = rd.nextInt();
  50.  
  51.         dfs(1);
  52.         pw.flush();
  53.     }
  54. }
  55.  
  56. class rd
  57. {
  58.     static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  59.     static StringTokenizer tokenizer = new StringTokenizer("");
  60.  
  61.     static String nextLine() throws IOException { return reader.readLine(); }
  62.     static String next() throws IOException
  63.     {
  64.         while(!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());
  65.         return tokenizer.nextToken();
  66.     }
  67.     static int nextInt() throws IOException { return Integer.parseInt(next()); }
  68.     static double nextDouble() throws IOException { return Double.parseDouble(next()); }
  69.     static long nextLong() throws IOException { return Long.parseLong(next()); }
  70.     static BigInteger nextBigInteger() throws IOException
  71.     {
  72.         BigInteger d = new BigInteger(rd.nextLine());
  73.         return d;
  74.     }
  75. }
  76.  
  77. class math
  78. {
  79.     int gcd(int a,int b)
  80.     {
  81.         if(b == 0)  return a;
  82.         else return gcd(b,a % b);
  83.     }
  84.  
  85.     int lcm(int a,int b)
  86.     {
  87.         return a * b / gcd(a, b);
  88.     }
  89.  
  90.     // 求n的所有约数
  91.     List get_factor(int n)
  92.     {
  93.         List<Long> a = new ArrayList<>();
  94.         for(long i = 1; i <= Math.sqrt(n) ; i ++)
  95.         {
  96.             if(n % i == 0)
  97.             {
  98.                 a.add(i);
  99.                 if(i != n / i)  a.add(n / i);  // // 避免一下的情况：x = 16时，i = 4 ，x / i = 4的情况，这样会加入两种情况  ^-^复杂度能减少多少是多少
  100.             }
  101.         }
  102.  
  103.         // 相同因子去重，这个方法，完美
  104.         a = a.stream().distinct().collect(Collectors.toList());
  105.  
  106.         // 对因子排序（升序）
  107.         Collections.sort(a);
  108.  
  109.         return a;
  110.     }
  111.  
  112.     // 判断是否是质数
  113.     boolean check_isPrime(int n)
  114.     {
  115.         if(n < 2) return false;
  116.         for(int i = 2 ; i <= n / i; i ++)  if (n % i == 0) return false;
  117.         return true;
  118.     }
  119. }
  120.  
  121. class PII implements Comparable<PII>
  122. {
  123.     int x,y;
  124.     public PII(int x ,int y)
  125.     {
  126.         this.x = x;
  127.         this.y = y;
  128.     }
  129.     public int compareTo(PII a)
  130.     {
  131.         if(this.x-a.x != 0)
  132.             return this.x-a.x;  //按x升序排序
  133.         else return this.y-a.y;  //如果x相同，按y升序排序
  134.     }
  135. }
  136.  
  137. class Edge
  138. {
  139.     int a,b,c;
  140.     public Edge(int a ,int b, int c)
  141.     {
  142.         this.a = a;
  143.         this.b = b;
  144.         this.c = c;
  145.     }
  146. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/434297
推荐阅读
相关标签

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

  

闽ICP备14008679号