1.算法概述

子集樹是一種?回溯算法，用于生成一個集合的所有子集。給定一個數組?arr，該算法遞歸地遍歷所有可能的子集，并通過一個輔助數組?x?標記當前元素是否被選中。

2.算法特點

• 時間復雜度：O(2n)（因為一個包含?n?個元素的集合有?2n?個子集）。

• 空間復雜度：O(n)（遞歸棧深度）。

• 適用場景：需要枚舉所有子集的問題，如組合、子集和、冪集等。

3.代碼實現

#include <iostream>
#include <string>

using namespace std;
void func(int arr[], int i, int length,int x[])
{
?? ?if (i == length)//遞歸終止條件：處理完所有元素
?? ?{
?? ??? ?for (int j = 0; j < length; j++)
?? ??? ?{
?? ??? ??? ?if (x[j] == 1)//如果當前元素被選中，則輸出
?? ??? ??? ??? ?cout << arr[j] << " ";
?? ??? ?}
?? ??? ?cout << endl;
?? ?}
?? ?else
?? ?{
?? ??? ?x[i] = 1;//選擇當前節點
?? ??? ?func(arr, i + 1, length,x);//處理左子樹
?? ??? ?x[i] = 0;//不選擇當前節點
?? ??? ?func(arr, i + 1, length,x);//處理右子樹
?? ?}
}
int main()
{
?? ?int arr[] = { 1,2,3 };
?? ?int length = sizeof(arr) / sizeof(int);
?? ?int x[3] = { 0 };//初始化數組為0
?? ?func(arr, 0, length,x);
?? ?return 0;
}

? ?在此列一道題目：在給出序列中，求所選元素和? 與 未選元素和的最小差值是多少

#include <iostream>??
#include <cmath>? ??

using namespace std;?

// 定義全局變量
int arr[] = { 12, 6, 7, 11, 16, 3, 9 }; ?// 輸入的數字數組
const int length = sizeof(arr) / sizeof(int); ?// 計算數組長度

int x[length] = { 0 }; ? // 記錄當前選擇的元素（1表示選中，0表示未選中）
int sum = 0; ? ? ? ? ? // 記錄當前已選元素的和
int r = 0; ? ? ? ? ? ? // 記錄當前未選元素的和
int Min = 0x7FFFFFFF; ?// 記錄最小差值，初始設為最大整數值
int bestx[length] = { 0 }; ?// 記錄最佳選擇方案

// 回溯函數
void func(int i) {
? ? // 遞歸終止條件：已處理完所有元素
? ? if (i == length) {
? ? ? ? // 計算當前選擇與未選擇子集和的絕對差值
? ? ? ? int result = abs(sum - r);

? ? ? ? // 如果找到更小的差值，更新最優解
? ? ? ? if (result < Min) {
? ? ? ? ? ? Min = result; ?// 更新最小差值
? ? ? ? ? ? // 保存當前最佳選擇方案
? ? ? ? ? ? for (int j = 0; j < length; j++) {
? ? ? ? ? ? ? ? bestx[j] = x[j];
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? else {
? ? ? ? // 選擇當前元素arr[i]的情況
? ? ? ? r -= arr[i]; ? ? ?// 從未選和中減去當前元素
? ? ? ? sum += arr[i]; ? ?// 將當前元素加到已選和
? ? ? ? x[i] = 1; ? ? ? ? // 標記當前元素為已選
? ? ? ? func(i + 1); ? ? ?// 遞歸處理下一個元素

? ? ? ? // 不選擇當前元素arr[i]的情況
? ? ? ? sum -= arr[i]; ? ?// 從已選和中減去當前元素
? ? ? ? r += arr[i]; ? ? ?// 將當前元素加到未選和
? ? ? ? x[i] = 0; ? ? ? ? // 標記當前元素為未選
? ? ? ? func(i + 1); ? ? ?// 遞歸處理下一個元素
? ? }
}

int main() {
? ? // 計算數組所有元素的總和，初始化未選和r
? ? for (int v : arr) {
? ? ? ? r += v;
? ? }

? ? // 從第0個元素開始回溯搜索
? ? func(0);

? ? // 輸出結果
? ? cout << "Selected: ";
? ? // 輸出被選中的元素
? ? for (int i = 0; i < length; i++) {
? ? ? ? if (bestx[i]) {
? ? ? ? ? ? cout << arr[i] << " ";
? ? ? ? }
? ? }
? ? // 輸出最小差值
? ? cout << "\nMin difference: " << Min << endl;

? ? return 0;?
}
?

繼續列一道題：給出2n個整數，從里面挑選n個整數，使其讓選擇的整數的和? 與未選擇的整數的和的差值最小

#include <iostream>?
#include <cmath>? ? ?
#include <vector>? ?

// 定義全局變量
int arr[] = {12,6,7,11,16,3,8,9}; ? ? ? ? ? // 輸入的數字數組
const int length = sizeof(arr)/sizeof(int); // 計算數組長度
std::vector<int> x; ? ? ? ? ? ? ? ? ? ? ? ? // 當前選擇的元素集合（存儲元素值）
std::vector<int> bestx; ? ? ? ? ? ? ? ? ? ? // 最佳選擇的元素集合
int sum; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 當前已選元素的和
int Left = length; ? ? ? ? ? ? ? ? ? ? ? ? // 剩余未處理的元素個數（初始為總長度）
int r; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 當前未選元素的和
unsigned int Min = INT_MAX; ? ? ? ? ? ? ? // 記錄最小差值（初始為最大整數值）
int cnt; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 記錄遞歸調用次數（調試用）

// 回溯函數（i表示當前處理元素的索引）
void func(int i) {
? ? // 遞歸終止條件：已處理完所有元素
? ? if (i == length) {
? ? ? ? cnt++; // 遞歸次數統計
? ? ? ??
? ? ? ? // 檢查是否恰好選中一半元素
? ? ? ? if (x.size() != length/2) return;
? ? ? ??
? ? ? ? // 計算當前差值
? ? ? ? int result = abs(sum - r);
? ? ? ??
? ? ? ? // 更新最優解
? ? ? ? if (result < Min) {
? ? ? ? ? ? Min = result; ? ?// 更新最小差值
? ? ? ? ? ? bestx = x; ? ? ? // 深拷貝當前選擇路徑
? ? ? ? }
? ? ? ? return;
? ? }
? ? // 未處理完所有元素時的遞歸操作
? ? else {
? ? ? ? Left--; // 減少剩余未處理元素數量
? ? ? ??
? ? ? ? // 分支1：選擇當前元素（需滿足選擇數量未過半）
? ? ? ? if (x.size() < length/2) { // 剪枝條件1：已選數量不能超過半數
? ? ? ? ? ? // 選擇當前元素
? ? ? ? ? ? sum += arr[i]; ? // 更新已選和
? ? ? ? ? ? r -= arr[i]; ? ? // 更新未選和
? ? ? ? ? ? x.push_back(arr[i]); // 記錄選擇路徑
? ? ? ? ? ??
? ? ? ? ? ? func(i+1); // 遞歸處理下一個元素
? ? ? ? ? ??
? ? ? ? ? ? // 回溯操作
? ? ? ? ? ? sum -= arr[i]; ? // 恢復已選和
? ? ? ? ? ? r += arr[i]; ? ? // 恢復未選和
? ? ? ? ? ? x.pop_back(); ? ?// 移除當前選擇
? ? ? ? }
? ? ? ??
? ? ? ? // 分支2：不選擇當前元素（需滿足剩余元素足夠湊夠半數）
? ? ? ? if (x.size() + Left >= length/2) { // 剪枝條件2：剩余元素足夠完成選擇
? ? ? ? ? ? func(i+1); // 遞歸處理下一個元素
? ? ? ? }
? ? ? ??
? ? ? ? Left++; // 恢復剩余未處理元素數量
? ? }
}

int main() {
? ? // 初始化未選和（總和）
? ? for(int num : arr) {
? ? ? ? r += num;
? ? }
? ??
? ? func(0); // 從第0個元素開始回溯
? ??
? ? // 輸出結果
? ? std::cout << "Selected elements: ";
? ? for(int v : bestx) {
? ? ? ? std::cout << v << " ";
? ? }
? ? std::cout << "\nMinimum difference: " << Min << std::endl;
? ? std::cout << "Total recursions: " << cnt << std::endl;?
? ??
? ? return 0;
}