前言
回溯法又稱為試探法，但當探索到某一步時，發現原先選擇達不到 目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法。

---

已知一組數(其中無重復元素)，求這組數可以組成的所有子集。 結果中不可有無重復的子集。
例如: nums[] = [1, 2, 3]
結果為: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

以上的初始數組集合中，每一個數在產生的子集中都有兩種可能：存在、不存在
那么最終的子集個數就為2^n,(n為初始數組的大小)

如果僅僅生成[1],[1,2],[1,2,3]這樣的集合，那么該如何實現呢？
過程如下：
方法一：使用普通的循環

std::vector<std::vector<int> > get_subsets2(std::vector<int> num) {std::vector<std::vector<int> > result; //存放最終的結果std::vector<int> item; //存放臨時數組for (int i = 0;i < num.size(); ++i) {item.push_back(num[i]);result.push_back(item);}return result;
}

方法二：使用回溯的遞歸實現

void generate(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) {if (i >= num.size()) {//結束條件即為遍歷到最后一個元素return ;}item.push_back(num[i]);result.push_back(item);generate(i + 1,num,item,result); //每一次對下標++
}std::vector<std::vector<int> > get_subsets(std::vector<int> num) {std::vector<std::vector<int> > result;std::vector<int> item;generate(0,num,item,result);return result;
}

那么接下來需要生成最終的2^3個數的子集
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

方法一：
回溯法生成子集，因為針對每一個元素，都只有兩種可能性，存在于子集或者不存在于子集之中，那么針對以上兩種可能性，都可以選擇遞歸進行后續元素的放入，每種元素同樣有兩種可能性，存在或者不存在；

例如 [1,2,3…]
針對元素1，有兩種可能性:
item = [1],后續繼續按照兩種可能進行下一個元素的存放: item = [1,2],item = [1] …
item = [],后續繼續按照兩種可能進行下一個元素的存放: item = [2],item = [] …

這個過程使用遞歸實現如下:

void generate2(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) {if (i >= num.size()) {return;}/*兩種可能：1. 放入當前元素2. 不放入當前元素*/item.push_back(num[i]);  //放入當前元素result.push_back(item);generate2(i+1, num, item, result); item.pop_back();// 不放入當前元素generate2(i+1, num, item, result);
}
/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> num) {std::vector<std::vector<int> > result;std::vector<int> item;result.push_back(item); //空元素提前放入generate2(0,num,item,result);return result;
}

方法二：
使用位運算符進行運算，過程如下：
因為針對每一種元素都有兩種可能，存在或者不存在；那么這個狀態可以用0或者1代替；
若一個集合有三個元素A, B, C，則3個元素有2^3 = 8 種組成 集合的方式，用0-7表示這些集合。即從000-111這個二進制范圍代替，每一位代表對應元素的存在狀態，0代表該元素不放入集合，1代表該元素放入了集合，總共有2^n種狀態。

構造A元素為100 = 4且1<<2 = 4 ，B元素為010 = 2且 1 << 1 = 2, C元素為001 = 1 且1 << 0 = 1，構造如下表格(表格中的按位與的結果并不是真正的與之后的數值，而是代表對應元素存在與否的真值):

集合	整數	A是否出現	B是否出現	C是否出現
{}	000=0	1 << 2 & 000 = 0	1 << 1 & 000 = 0	1 << 0 & 000 = 0
{C}	001=1	1 << 2 & 001 = 0	1 << 1 & 001 = 0	1 << 0 & 001 = 1
{B}	010=2	1 << 2 & 010 = 0	1 << 1 & 010 = 1	1 << 0 & 010 = 0
{B,C}	011=3	1 << 2 & 011 = 0	1 << 1 & 011 = 1	1 << 0 & 011 = 1
{A}	100=4	1 << 2 & 100 = 1	1 << 1 & 100 = 0	1 << 0 & 100 = 0
{A,C}	101=5	1 << 2 & 101 = 1	1 << 1 & 101 = 0	1 << 0 & 101 = 1
{A,B}	110=6	1 << 2 & 110 = 1	1 << 1 & 110 = 1	1 << 0 & 110 = 0
{A,B,C}	111=7	1 << 2 & 111 = 1	1 << 1 & 111=1	1 << 0 & 111 = 1

實現過程如下:

/*method2*/
std::vector<std::vector<int> > generate3(std::vector<int> &num){std::vector<std::vector<int> > result;int all_set = 1 << num.size();for (int i = 0;i < all_set; ++i) {//遍歷所有可能的結果std::vector<int> item;for (int j = 0;j < num.size(); ++j) {if (i & (1 << j)) { //通過一一比對，核對最終j下標代表的元素是否存在item.push_back(num[j]);}}result.push_back(item);}return result;
}

測試代碼如下:

#include <iostream>
#include <vector>
#include <algorithm>/*
Subsets已知一組數(其中無重復元素)，求這組數可以組成的所有子集。 結果中不可有無重復的子集。
例如: nums[] = [1, 2, 3]
結果為: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
*/using namespace std;
void generate(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) {if (i >= num.size()) {return ;}item.push_back(num[i]);result.push_back(item);generate(i + 1,num,item,result);
} std::vector<std::vector<int> > get_subsets2(std::vector<int> num) {std::vector<std::vector<int> > result;std::vector<int> item;result.push_back(item);for (int i = 0;i < num.size(); ++i) {item.push_back(num[i]);result.push_back(item);}return result;
}void generate2(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) {if (i >= num.size()) {return;}item.push_back(num[i]);result.push_back(item);generate2(i+1, num, item, result);item.pop_back();generate2(i+1, num, item, result);
}/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> num) {std::vector<std::vector<int> > result;std::vector<int> item;result.push_back(item);generate2(0,num,item,result);return result;
}/*method2*/
std::vector<std::vector<int> > generate3(std::vector<int> &num){std::vector<std::vector<int> > result;int all_set = 1 << num.size();for (int i = 0;i < all_set; ++i) {std::vector<int> item;for (int j = 0;j < num.size(); ++j) {if (i & (1 << j)) {item.push_back(num[j]);}}result.push_back(item);}return result;
}	int main(int argc, char const *argv[])
{std::vector<int> num;std::vector<int> item;std::vector<std::vector<int>> result1;std::vector<std::vector<int>> result2;int tmp;int N;std::cin >> N;for (int i  = 0;i < N; ++i) {std::cin >> tmp;num.push_back(tmp);}result1= get_subsets(num);result2= generate3(num);cout << "method1 " << endl;for (int i = 0;i < result1.size(); ++i) {if (result1[i].size() == 0) {cout << "[]";}for (int j = 0;j < result1[i].size(); ++j) {std::cout << "[" << result1[i][j] << "] ";}std::cout << std::endl;}cout << "method2 " << endl;for (int i = 0;i < result2.size(); ++i) {if (result2[i].size() == 0) {cout << "[]";}for (int j = 0;j < result2[i].size(); ++j) {std::cout << "[" << result2[i][j] << "] ";}std::cout << std::endl;}return 0;
}

輸出如下:

3
1 2 3
method1 
[]
[1] 
[1] [2] 
[1] [2] [3] 
[1] [3] 
[2] 
[2] [3] 
[3] 
method2 
[]
[1] 
[2] 
[1] [2] 
[3] 
[1] [3] 
[2] [3] 
[1] [2] [3] 

可以看到遞歸回溯遍歷的結果和位運算遍歷到的結果輸出順序上是有差異的，遞歸回溯需要一直遍歷到最終的尾元素，而位運算則是遍歷過程中一個一個添加。

總結

以上是生活随笔為你收集整理的递归/回溯：subsets求子集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。