前言

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

題目

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

例子：

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

解法

解法一

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

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

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

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

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

因此當(dāng)我們選中的元素達(dá)到k個(gè)的時(shí)候，我們就可以退出遞歸，因此這是我們的一個(gè)遞歸出口，我們?cè)谠O(shè)計(jì)回溯函數(shù)的時(shí)候需要實(shí)現(xiàn)這個(gè)出口。

除了上面提到的遞歸出口之外我們還有另外一個(gè)隱藏的遞歸出口。當(dāng)我們當(dāng)前選擇的數(shù)據(jù)的個(gè)數(shù)加上后面還剩下的所有的數(shù)據(jù)的時(shí)候還達(dá)不到我們所需要的數(shù)據(jù)的個(gè)數(shù)k的時(shí)候，我們也不需要在進(jìn)行遍歷了，可以直接退出遞歸了，比如上面用紅色標(biāo)記的節(jié)點(diǎn)，因?yàn)榧词辜由狭撕竺媸Ｓ嗟乃械臄?shù)據(jù)也不能夠滿足條件。

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

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

解法二

除了上面的實(shí)現(xiàn)方式之外，我們還有另外一種方式實(shí)現(xiàn)選和不選的操作。如果我們不選一個(gè)數(shù)據(jù)的話表示我們?cè)诤竺鎸?duì)數(shù)據(jù)的選擇過(guò)程當(dāng)中就不會(huì)選到這個(gè)數(shù)據(jù)了，我們另外一種實(shí)現(xiàn)方式如下所示，可能看代碼不能夠很好的理解，可以結(jié)合后面的問(wèn)題和圖進(jìn)行理解：

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

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

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

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

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

前面三個(gè)節(jié)點(diǎn)表示選擇數(shù)據(jù)3得到的所有的結(jié)果，第三個(gè)節(jié)點(diǎn)之后所有的節(jié)點(diǎn)表示不選擇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++實(shí)現(xiàn)

實(shí)現(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);
    }
};

實(shí)現(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();
      }
    }
};

總結(jié)

根據(jù)上面所提到的解法，我們可以總結(jié)回溯算法題的一般規(guī)律：

回溯算法一般是遞歸算法，因此我們需要有遞歸出口。我們?cè)谠O(shè)計(jì)遞歸函數(shù)的時(shí)候，需要注意遞歸出口，同時(shí)需要仔細(xì)檢查是否能夠進(jìn)行剪枝，其實(shí)所謂的剪枝就是增加新的遞歸出口。

很多回溯問(wèn)題都可以轉(zhuǎn)化為對(duì)數(shù)據(jù)進(jìn)行選擇和不選擇操作。

回溯之所以被稱(chēng)作回溯是因?yàn)槲覀冊(cè)趯?shí)現(xiàn)程序的時(shí)候當(dāng)我們選擇一個(gè)數(shù)據(jù)之后還需要進(jìn)行不選擇的操作，而這個(gè)不選擇的操作需要將集合中數(shù)據(jù)中的狀態(tài)退回到上一步，這個(gè)退回到上一步的過(guò)程就叫做回溯。

以上就是通過(guò)Java組合問(wèn)題看透回溯法的詳細(xì)內(nèi)容，更多關(guān)于Java回溯法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論