本文主要講解組合的要點與細節，以及回溯算法的解題步驟，按照步驟思考更方便理解?

c++和java代碼如下，末尾

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

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

?具體要點：

1. 首先，這道題的暴力解法是k層for循環，遍歷所有的情況。但是這樣子時間復雜度會很高。所以對于這類排列組合的問題，通常我們使用回溯算法來進行遍歷，可以花一分鐘參考回溯的前言概述。

---

2. 然后讓我們來回顧一下回溯，回溯本質是一個樹結構通常是由兩個結構組成：for+遞歸。

? ? ? ? 其中，for用來表示樹的寬度，遍歷每層的集合元素集，可以理解一個節點有多少個孩子，這個for循環就執行多少次。

? ? ? ? 遞歸用來表示樹的深度

---

3. 對于本題要求，我們需要先創建兩個數組，一個用來存放最終的結果，一個用來存放過程中每次的結果

vector<vector<int>> res; //用來存放最終的結果
vector<int> temp; //用來存放過程中每次的結果

---

?4. 接著我們就可以考慮回溯算法的實現，具體包括兩部分：for循環+遞歸

首先，我們來考慮遞歸，說到遞歸，就要思考遞歸三要素：

• 遞歸函數參數與返回值
• 終止條件
• 單層遞歸邏輯

返回值：由于我們是直接操作數組，不像二叉樹一樣需要返回節點，所以遞歸的返回值是void

參數：回溯算法中的遞歸參數較多，我們在寫代碼過程中慢慢添加

終止條件：也就是我們收集結果的條件，當我們的temp存放的數量等于k時，就需要收集結果了

單層遞歸邏輯：添加當前元素a到temp中——a向下遞歸——移除剛才添加的元素a

其次，讓我們考慮一下for循環的細節

? ? ? ? for循環的起始值應該是什么呢？

? ? ? ? 這個細節是回溯中重要的點，因為本題是“組合”，所以不需要順序，即{1，2}和{2，1}是一個意思，只保留一個，所以下一層遞歸時，起始值就+1，從而達到去重的目的。

    void backtracing(int n, int k,vector<vector<int>>& res, vector<int> temp,int start) {//終止條件if (temp.size() == k) {//收集結果res.push_back(temp);return;}for (int i = start; i <= n; ++i) {temp.push_back(i);//添加當前元素backtracing(n, k, res, temp, i + 1);//相下遞歸，起始值+1temp.pop_back();//刪除剛才添加的元素，實現回溯}return;}

---

以上就是回溯的整體邏輯，讓我們總結一下重要的細節：

• 遞歸的返回值
• 遞歸的終止條件
• for循環的起始值

在回溯過程中大家重點思考一下這幾個細節點，有助于我們更好的實現代碼

如果覺得我的講解有一點幫助，十分感謝您的喜歡。

c++代碼：

#include<bits/stdc++.h>
using namespace std;class Solution {
public:vector<vector<int>> combine(int n, int k) {//組合，不考慮順序vector<vector<int>> res;vector<int> temp;backtracing(n, k, res, temp, 1);return res;}void backtracing(int n, int k,vector<vector<int>>& res, vector<int> temp,int start) {//終止條件if (temp.size() == k) {//收集結果res.push_back(temp);return;}for (int i = start; i <= n; ++i) {temp.push_back(i);//添加當前元素backtracing(n, k, res, temp, i + 1);//相下遞歸temp.pop_back();//刪除剛才添加的元素，實現回溯}return;}};

java代碼

class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<>();backtracking(n, k, res, temp, 1);return res;}public void backtracking(int n, int k, List<List<Integer>> res, List<Integer> temp, int start) {//終止條件if (temp.size() == k) {res.add(new ArrayList<>(temp));return;}for (int i = start; i <= n; i++) {temp.add(i);backtracking(n, k, res, temp, i + 1);temp.remove(temp.size() - 1);}return;}
}