DFS中的递归问题

汉诺塔

• 题目地址：面试题 08.06. 汉诺塔问题
  

• Java 代码

  // 递归版本一
  class Solution {
      public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
          int n = A.size();
          dfs(A, B, C, n);
          return;
      }
  
      private void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
          if (n == 1) {
              c.add(a.remove(a.size() - 1));
          } else {
              dfs(a, c, b, n - 1);
              c.add(a.remove(a.size() - 1));
              dfs(b, a, c, n - 1);
          }
      }
  }
  
  // 递归版本二
  class Solution {
      public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
          int n = A.size();
          dfs(A, B, C, n);
          return;		
      }
  
      private void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
          if (n == 1) {
              c.add(a.remove(a.size() - 1));
              return;    // 这里必须有，不然栈溢出！
          }
  
          dfs(a, c, b, n - 1);
          c.add(a.remove(a.size() - 1));
          dfs(b, a, c, n - 1);
      }
  }
  

  时间复杂度：$O(2^n - 1)$，其中 $n$ 为圆盘数量。

• 参考链接：

  • 有趣的汉诺塔游戏怎么玩？把大象放冰箱里一共分几步？

  • 「递归练习」汉诺塔

  • 汉诺塔

  • 输出移动汉诺塔步骤的非递归程序

  • 汉诺塔问题的递归和非递归算法详细讲解

分支污染问题

理解 本贴 分支污染问题 和 递归分支污染对结果的影响。

• Java 代码

  // 体会分支污染问题
  class Solution {
      public List<List<Integer>> combinationSum(int[] candidates, int target) {
          List<Integer> cur = new ArrayList<>();
          dfs(cur, candidates, target);
          return res;
      }
  
      private void dfs(List<Integer> cur, int[] a, int target) {
          if (target == 0) {
              res.add(new ArrayList<>(cur));
              return;
          }
  
          for (int i = 0; i < a.length; i++) {
              if (target < a[i]) continue;
              cur.add(a[i]);
              dfs(cur, a, target - a[i]);
          }
      }
  
      private List<List<Integer>> res = new ArrayList<>();
  }
  
  // 解决分支污染问题
  class Solution {
      public List<List<Integer>> combinationSum(int[] candidates, int target) {
          List<Integer> cur = new ArrayList<>();
          dfs(cur, candidates, target);
          return res;
      }
  
      private void dfs(List<Integer> cur, int[] a, int target) {
          if (target == 0) {
              res.add(new ArrayList<>(cur));
              return;
          }
  
          for (int i = 0; i < a.length; i++) {
              if (target < a[i]) continue;
              List<Integer> list = new ArrayList<>(cur);
              list.add(a[i]);
              dfs(list, a, target - a[i]);
          }
      }
  
      private List<List<Integer>> res = new ArrayList<>();
  }
  
  // 也可以这样写
  class Solution {
      public List<List<Integer>> combinationSum(int[] candidates, int target) {
          List<Integer> cur = new ArrayList<>();
          dfs(cur, candidates, target);
          return res;
      }
  
      private void dfs(List<Integer> cur, int[] a, int target) {
          if (target == 0) {
              res.add(new ArrayList<>(cur));
              return;
          }
  
          for (int i = 0; i < a.length; i++) {
              if (target < a[i]) continue;
              cur.add(a[i]);
              dfs(cur, a, target - a[i]);
              cur.remove(cur.size() - 1);	// 利用回溯解决分支污染问题
          }
      }
  
      private List<List<Integer>> res = new ArrayList<>();
  }
  

体会

关键还是画出递归树，有递归树就很好写了。