77. 組合
77. 組合
難度：中等
給定兩個整數 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]]
回溯法解題思路：
回溯法，一般可以解決如下幾種問題：
組合問題：N個數里面按一定規則找出k個數的集合
切割問題：一個字串按一定規則有幾種切割方式
子集問題：一個N個數的集合里有多少符合條件的子集
排列問題：N個數按一定規則全排列，有幾種排列方式
棋盤問題：N皇后，解數獨等等
另外，會有一些同學可能分不清什么是組合，什么是排列？
組合是不強調元素順序的，排列是強調元素順序，
例如：{1, 2} 和 {2, 1} 在組合上，就是一個集合，因為不強調順序，而要是排列的話，{1, 2} 和 {2, 1} 就是兩個集合了，
記住組合無序，排列有序，就可以了，
回溯法解決的問題都可以抽象為樹形結構，是的，我指的是所有回溯法的問題都可以抽象為樹形結構！
因為回溯法解決的都是在集合中遞回查找子集，集合的大小就構成了樹的寬度，遞回的深度，都構成的樹的深度，
回溯演算法模板框架如下：
//這份模板很重要，后面做回溯法的題目都靠它了！
void backtracking(引數) {
if (終止條件) {
存放結果;
return;
}
for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {
處理節點;
backtracking(路徑，選擇串列); // 遞回
回溯，撤銷處理結果
}
}
剪枝優化
我們說過，回溯法雖然是暴力搜索，但也有時候可以有點剪枝優化一下的，
在遍歷的程序中有如下代碼：
for (int i = startIndex; i <= n; i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
這個遍歷的范圍是可以剪枝優化的，怎么優化呢？
來舉一個例子，n = 4，k = 4的話，那么第一層for回圈的時候，從元素2開始的遍歷都沒有意義了，在第二層for回圈，從元素3開始的遍歷都沒有意義了，
這么說有點抽象，如圖所示：
圖中每一個節點（圖中為矩形），就代表本層的一個for回圈，那么每一層的for回圈從第二個數開始遍歷的話，都沒有意義，都是無效遍歷，
所以，可以剪枝的地方就在遞回中每一層的for回圈所選擇的起始位置，
如果for回圈選擇的起始位置之后的元素個數 已經不足 我們需要的元素個數了，那么就沒有必要搜索了，
接下來看一下優化程序如下：
已經選擇的元素個數：path.size();
還需要的元素個數為: k - path.size();
在集合n中至多要從該起始位置 : n - (k - path.size()) + 1，開始遍歷
為什么有個+1呢，因為包括起始位置，我們要是一個左閉的集合，
舉個例子，n = 4，k = 3， 目前已經選取的元素為0（path.size為0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2，
從2開始搜索都是合理的，可以是組合[2, 3, 4]，
這里大家想不懂的話，建議也舉一個例子，就知道是不是要+1了，
所以優化之后的for回圈是：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i為本次搜索的起始位置
代碼
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>>res;
vector<int>tem;
backtracking(n,k,1,tem,res);
return res;
}
//回溯演算法
void backtracking(int n,int k,int startindex,vector<int>& tem,vector<vector<int>>& res)
{
//比如1，2已經滿足條件則加入res,遞回回傳
if (tem.size()==k)
{
res.push_back(tem);
return;
}
else
{
//這一步可以進行剪枝操作
// for(int i=startindex;i<=n;i++)
for(int i=startindex;i<=n-(k-tem.size())+1;i++)
{
tem.push_back(i);
backtracking(n,k,i+1,tem,res);
tem.pop_back(); //這步很關鍵
}
}
}
};
以上內容摘自微信公眾號：代碼隨想錄
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/459555.html
標籤：其他
上一篇：音頻內容理解的關鍵技術