通過Java組合問題看透回溯法

更新時間：2022年09月21日 09:13:26 作者：一無是處的研究僧

今天給大家分享一道LeetCode算法題，題目不是很困難，但是從這到簡單的題目我們可以分析出回溯算法的幾個核心要點，感興趣的可以了解一下

前言

已經(jīng)好久沒有更新了??，從今天開始要保證每周的更新頻率了（立個flag，應該能夠想到打臉會來的很快??），今天給大家分享一道LeetCode算法題，題目不是很困難，但是從這到簡單的題目我們可以分析出回溯算法的幾個核心要點，以后遇到需要回溯的題目可以應對的思路，知道應該怎么思考，朝什么方向去尋找解決問題的出口！

題目

給定兩個整數(shù) n 和 k，返回范圍 [1, n] 中所有可能的 k 個數(shù)的組合。你可以按任何順序返回答案。

例子：

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

解法

解法一

乍一看這道題好像是一個很直接的問題，我們只需要從[1, n]當中選出k個數(shù)據(jù)出來，比如說題目當中給出的，我們需要從[1, 4]這個區(qū)間取出兩個數(shù)，那么我們只需要使用兩層for循環(huán)即可，像下面這樣：

for (int i = 1; i <= n; i++) {
      // 在這里選擇 i 
    for (int j = i + 1; j <= n; j++) {
        // 每一次循環(huán)選擇 j 
    }
}

但是遺憾的是k是一個變量，它不是一個定值，如果他是一個定值的話，那么我們就可以使用上面的循環(huán)操作去解決這個問題，而且是很高效的。那這個問題我們應該如何解決的？我們思考一下，對于每一個數(shù)我們都有兩種選擇：選擇和不選擇，也就是是否需要將這個數(shù)據(jù)加到集合當中去。

現(xiàn)在我們對上述給定的例子進行求解（n = 4, k = 2），每一個數(shù)據(jù)都有兩種選擇，選和不選（很多回溯的問題都是可以按照這種思路）具體過程入下圖所示，其中藍色的節(jié)點表示待選擇的數(shù)據(jù)，紅色的框表示當前被選中的數(shù)據(jù)的集合：

上圖是上文當中給出的例子的解樹，其中綠色的節(jié)點表示最終的答案，對于每個節(jié)點的數(shù)據(jù)都有兩種選擇辦法，選和不選，因此上面的解決問題的樹結(jié)構(gòu)是一個完全二叉樹，我們可以使用深度優(yōu)先遍歷去實現(xiàn)上面的解題過程。從上圖來看我們可以進行一些剪枝，當我們選中的數(shù)據(jù)的個數(shù)已經(jīng)達到k的時候我們不需要在進行遞歸，因為我們需要的數(shù)據(jù)長度是固定的，當達到指定數(shù)目的數(shù)據(jù)個數(shù)之后我們不需要再加入數(shù)據(jù)了，因此也沒有繼續(xù)往下遍歷的必要了。具體看下圖，其中紫色節(jié)點表示不需要進行遞歸的節(jié)點，因為在遍歷他們之前我們都已經(jīng)得到一個結(jié)果了：

因此當我們選中的元素達到k個的時候，我們就可以退出遞歸，因此這是我們的一個遞歸出口，我們在設(shè)計回溯函數(shù)的時候需要實現(xiàn)這個出口。

除了上面提到的遞歸出口之外我們還有另外一個隱藏的遞歸出口。當我們當前選擇的數(shù)據(jù)的個數(shù)加上后面還剩下的所有的數(shù)據(jù)的時候還達不到我們所需要的數(shù)據(jù)的個數(shù)k的時候，我們也不需要在進行遍歷了，可以直接退出遞歸了，比如上面用紅色標記的節(jié)點，因為即使加上了后面剩余的所有的數(shù)據(jù)也不能夠滿足條件。

根據(jù)上面我們的思路和兩個遞歸出口，我們可以寫出下面的代碼：

public void backTrace(int n, int k, List<Integer> path,
                      int idx) {
  // idx 表示當前正在遍歷的數(shù)據(jù)
  if (path.size() == k){ // 如果選中的數(shù)據(jù)個數(shù)達到 k 了那么我們需要將當前選中數(shù)據(jù)的集合加入到我們返回的數(shù)據(jù)當中 ans 表示我們最終需要返回的結(jié)果 里面的內(nèi)容是 有 k 個數(shù)據(jù)的集合
    ans.add(new ArrayList<>(path));
    return;
  } else if ((path.size() + n - idx + 1) < k)
    return;
  path.add(idx); // 加入一個數(shù)據(jù) 表示選擇數(shù)據(jù) idx
  backTrace(n, k, path, idx + 1);
  path.remove(path.size() - 1); // 移出上面加入的數(shù)據(jù) 表示在這里進行回溯 因為我們是深度優(yōu)先遍歷，前面將 idx 加入到了 path 當中 當遞歸返回的時候我們需要將加入的數(shù)據(jù)移出 因為這里表示不選擇數(shù)據(jù) 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);
  }
 
}

解法二

除了上面的實現(xiàn)方式之外，我們還有另外一種方式實現(xiàn)選和不選的操作。如果我們不選一個數(shù)據(jù)的話表示我們在后面對數(shù)據(jù)的選擇過程當中就不會選到這個數(shù)據(jù)了，我們另外一種實現(xiàn)方式如下所示，可能看代碼不能夠很好的理解，可以結(jié)合后面的問題和圖進行理解：

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);
  }
}

在上面的圖當中，數(shù)據(jù)1在第一個節(jié)點出現(xiàn)之后不會在后面的節(jié)點再出現(xiàn)了，數(shù)據(jù)2在第二個節(jié)點出現(xiàn)之后就不會在出現(xiàn)了，數(shù)據(jù)3在第三個節(jié)點出現(xiàn)之后就不會在出現(xiàn)了，......

可能你會有疑問為什么是這樣？為什么這樣進行選擇和選和不選得到的結(jié)果一樣呢？

其實第一個節(jié)點就是選擇數(shù)據(jù)1得到的所有的結(jié)果，表示選擇數(shù)據(jù)1，后面的所有的節(jié)點就表示不選擇數(shù)據(jù)1。

前面兩個節(jié)點表示選擇數(shù)據(jù)2得到的所有的結(jié)果，第二個節(jié)點之后的所有節(jié)點表示不選擇2得到的結(jié)果。

前面三個節(jié)點表示選擇數(shù)據(jù)3得到的所有的結(jié)果，第三個節(jié)點之后所有的節(jié)點表示不選擇3得到的結(jié)果。

使用第二種方法的完整代碼：

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++實現(xiàn)

實現(xiàn)方式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);
    }
};

實現(xiàn)方式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();
      }
    }
};