关于回溯法:通过组合问题看透回溯法

通过组合问题看透回溯法

前言

曾经良久没有更新了🤣，从明天开始要保障每周的更新频率了（立个 flag，应该可能想到打脸会来的很快😂），明天给大家分享一道 LeetCode 算法题，题目不是很艰难，然而从这到简略的题目咱们能够剖析出回溯算法的几个外围要点，当前遇到须要回溯的题目能够应答的思路，晓得应该怎么思考，朝什么方向去寻找解决问题的进口！

题目

给定两个整数 n 和 k，返回范畴 [1, n] 中所有可能的 k 个数的组合。你能够按 任何程序 返回答案。

例子：

输出：n = 4, k = 2
输入：[[2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解法

解法一

乍一看这道题如同是一个很间接的问题，咱们只须要从 [1, n] 当中选出 k 个数据进去，比如说题目当中给出的，咱们须要从 [1, 4] 这个区间取出两个数，那么咱们只须要应用两层 for 循环即可，像上面这样：

for (int i = 1; i <= n; i++) {
      // 在这里抉择 i 
    for (int j = i + 1; j <= n; j++) {// 每一次循环抉择 j}
}

然而遗憾的是 k 是一个变量，它不是一个定值，如果他是一个定值的话，那么咱们就能够应用下面的循环操作去解决这个问题，而且是很高效的。那这个问题咱们应该如何解决的？咱们思考一下，对于每一个数咱们都有两种抉择：抉择和不抉择，也就是是否须要将这个数据加到汇合当中去。

当初咱们对上述给定的例子进行求解（n = 4, k = 2），每一个数据都有两种抉择，选和不选（很多回溯的问题都是能够依照这种思路）具体过程入下图所示，其中蓝色的节点示意待抉择的数据，红色的框示意以后被选中的数据的汇合：

上图是上文当中给出的例子的解树，其中绿色的节点示意最终的答案，对于每个节点的数据都有两种抉择方法，选和不选，因而下面的解决问题的树结构是一个齐全二叉树，咱们能够应用 深度优先遍历 去实现下面的解题过程。从上图来看咱们能够进行一些剪枝，当咱们选中的数据的个数曾经达到 k 的时候咱们不须要在进行递归，因为咱们须要的数据长度是固定的，当达到指定数目的数据个数之后咱们不须要再退出数据了，因而也没有持续往下遍历的必要了。具体看下图，其中紫色节点示意不须要进行递归的节点，因为在遍历他们之前咱们都曾经失去一个后果了：

因而当咱们选中的元素达到 k 个的时候，咱们就能够退出递归，因而这是咱们的一个递归进口，咱们在设计回溯函数的时候须要实现这个进口。

除了下面提到的递归进口之外咱们还有另外一个暗藏的递归进口。当咱们以后抉择的数据的个数加上前面还剩下的所有的数据的时候还达不到咱们所须要的数据的个数 k 的时候，咱们也不须要在进行遍历了，能够间接退出递归了，比方下面用红色标记的节点，因为即便加上了前面残余的所有的数据也不可能满足条件。

依据下面咱们的思路和两个递归进口，咱们能够写出上面的代码：

public void backTrace(int n, int k, List<Integer> path,
                      int idx) {
  // idx 示意以后正在遍历的数据
  if (path.size() == k){ // 如果选中的数据个数达到 k 了那么咱们须要将以后选中数据的汇合退出到咱们返回的数据当中 ans 示意咱们最终须要返回的后果 外面的内容是 有 k 个数据的汇合
    ans.add(new ArrayList<>(path));
    return;
  } else if ((path.size() + n - idx + 1) < k)
    return;
  path.add(idx); // 退出一个数据 示意抉择数据 idx
  backTrace(n, k, path, idx + 1);
  path.remove(path.size() - 1); // 移出下面退出的数据 示意在这里进行回溯 因为咱们是深度优先遍历，后面将 idx 退出到了 path 当中 当递归返回的时候咱们须要将退出的数据移出 因为这里示意不抉择数据 idx 
  backTrace(n, k, path, idx + 1);
}

残缺代码如下：

class Solution {private List<List<Integer>> ans = new ArrayList<>();

  public List<List<Integer>> combine(int n, int k) {backTrace(n, k, new ArrayList<>(), 1);
    return ans;
  }

  public void backTrace(int n, int k, List<Integer> path,
                        int idx) {if (path.size() == k){ans.add(new ArrayList<>(path));
      return;
    } else if ((path.size() + n - idx + 1) < k)
      return;
    path.add(idx);
    backTrace(n, k, path, idx + 1);
    path.remove(path.size() - 1);
    backTrace(n, k, path, idx + 1);
  }

}

办法二

除了下面的实现形式之外，咱们还有另外一种形式实现 选和不选 的操作。如果咱们不选一个数据的话示意咱们在前面对数据的抉择过程当中就不会选到这个数据了，咱们另外一种实现形式如下所示，可能看代码不可能很好的了解，能够联合前面的问题和图进行了解：

public void backtrace(int n, int k,
                      int startPosition) {if (path.size() == k) {res.add(new ArrayList<>(path));
    return;
  }
  for (int i = startPosition; i <= n; i++) {path.add(i);
    backtrace(n, k, i + 1);
    path.remove(path.size() - 1);
  }
}

在下面的图当中，数据 1 在第一个节点呈现之后不会在前面的节点再呈现了，数据 2 在第二个节点呈现之后就不会在呈现了，数据 3 在第三个节点呈现之后就不会在呈现了，……

可能你会有疑难为什么是这样？为什么这样进行抉择和 选和不选 失去的后果一样呢？

• 其实第一个节点就是抉择数据 1 失去的所有的后果，示意抉择数据 1，前面的所有的节点就示意不抉择数据 1。
• 后面两个节点示意抉择数据 2 失去的所有的后果，第二个节点之后的所有节点示意不抉择 2 失去的后果。
• 后面三个节点示意抉择数据 3 失去的所有的后果，第三个节点之后所有的节点示意不抉择 3 失去的后果。

应用第二种办法的残缺代码：

class Solution {private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {backtrace(n, k, 1);
        return res;
    }

    public void backtrace(int n, int k,
                          int startPosition) {if (path.size() == k) {res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startPosition; i <= n; i++) {path.add(i);
            backtrace(n, k, i + 1);
            path.remove(path.size() - 1);
        }
    }

}

C++ 实现

实现形式 1

class Solution {
    vector<vector<int>> ans;
public:
    vector<vector<int>> combine(int n, int k) {backtrace(n, k, vector<int>());
      return ans;
    }

    void backtrace(int n, int k, vector<int> tmp, int cur=1) {if (tmp.size() == k) {ans.push_back(tmp);
        return;
      }
      if (tmp.size() + (n - cur) + 1 < k)
        return;
      tmp.push_back(cur);
      backtrace(n, k, tmp, cur + 1);
      tmp.pop_back();
      backtrace(n ,k, tmp, cur + 1);
    }
};

实现形式 2

#include <vector>

using namespace std;
class Solution {
    vector<vector<int>> ans;
public:
    vector<vector<int>> combine(int n, int k) {backtrace(n, k, vector<int>());
      return ans;
    }

    void backtrace(int n, int k, vector<int> tmp, int cur=1) {if (tmp.size() == k) {ans.push_back(tmp);
        return;
      }
      for (int i = cur; i <= n - (k - tmp.size()) + 1 ; ++i) {tmp.push_back(i);
        backtrace(n, k, tmp, i + 1);
        tmp.pop_back();}
    }
};

总结

依据下面所提到的解法，咱们能够总结回溯算法题的个别法则：

• 回溯算法个别是递归算法，因而咱们须要有递归进口。咱们在设计递归函数的时候，须要留神递归进口，同时须要仔细检查是否可能进行剪枝，其实所谓的剪枝就是减少新的递归进口。
• 很多回溯问题都能够转化为对数据进行 抉择和不抉择 操作。
• 回溯之所以被称作回溯是因为咱们在实现程序的时候当咱们抉择一个数据之后还须要进行不抉择的操作，而这个不抉择的操作须要将汇合中数据中的状态退回到上一步，这个退回到上一步的过程就叫做 回溯。

以上就是本篇文章的所有内容了，我是LeHung，咱们下期再见！！！更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。