???????📝個人主頁：五敷有你? ? ??

?🔥系列專欄：算法分析與設計

??穩中求進，曬太陽

題目

給定兩個整數?n?和?k，返回范圍?[1, n]?中所有可能的?k?個數的組合。

你可以按?任何順序?返回答案。

示例

示例 1：

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

示例 2：

輸入：n = 1, k = 1
輸出：[[1]]

思路(回溯+剪枝)

????????如果解決一個問題有多個步驟，每一個步驟有多種方法，題目又要我們找出所有的方法，可以使用回溯算法；
????????回溯算法是在一棵樹上的 深度優先遍歷（因為要找所有的解，所以需要遍歷）；
????????組合問題，相對于排列問題而言，不計較一個組合內元素的順序性（即 [1, 2, 3] 與 [1, 3, 2] 認為是同一個組合），因此很多時候需要按某種順序展開搜索，這樣才能做到不重不漏。
????????回溯算法首先需要畫出遞歸樹，不同的樹決定了不同的代碼實現。下面給出了兩種畫樹的思路。

根據搜索起點畫出二叉樹

????????既然是樹形問題上的 深度優先遍歷，因此首先畫出樹形結構。例如輸入：n = 4, k = 2，我們可以發現如下遞歸結構：

????????如果組合里有 1 ，那么需要在 [2, 3, 4] 里再找 1 個數；
????????如果組合里有 2 ，那么需要在 [3, 4] 里再找 1數。注意：這里不能再考慮 1，因為包含 1 的組合，在第 1 種情況中已經包含。
????????依次類推（后面部分省略），以上描述體現的 遞歸 結構是：在以 n 結尾的候選數組里，選出若干個元素。畫出遞歸結構如下圖：

說明：

????????葉子結點的信息體現在從根結點到葉子結點的路徑上，因此需要一個表示路徑的變量 path，它是一個列表，特別地，path 是一個棧；
????????每一個結點遞歸地在做同樣的事情，區別在于搜索起點，因此需要一個變量 start ，表示在區間 [begin, n] 里選出若干個數的組合；
????????對于這一類問題，畫圖幫助分析是非常重要的解題方法。

代碼實現

class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<>();if (k <= 0 || n < k) {return res;}// 從 1 開始是題目的設定Deque<Integer> path = new ArrayDeque<>();dfs(n, k, 1, path, res);return res;}public static void dfs(int n,int k,int begin,Deque<Integer> path,List<List<Integer>> res){//遞歸中止條件 path長度為kif(path.size()==k){res.add(new ArrayList<>(path));return;}//遍歷所有可能的起點for(int i=begin;i<=n;i++){//向路徑變量里添加一個數字path.addLast(i);dfs(n,k,i+1,path,res);path.removeLast();}}
}

運行結果