c130 - 00574 - Sum It Up
題目描述
題目要求找出一個給定的正整數集合，所有加總等於目標值 t 的子集組合。輸出所有可能的組合，並按照特定規則排序。如果找不到任何組合，則輸出 "NONE"。
解題思路
本題採用遞迴回溯法 (Backtracking) 解決。dfs 函數從給定的數組中選擇數字，嘗試將它們加總到目標值 t。
- 遞迴的基礎情況是當目前的總和等於 t 時，將找到的子集存儲到一個
set中。使用set可以自動去除重複的組合。 - 在遞迴過程中，從當前索引
it開始，遍歷數組中的每個數字。如果將當前數字加到總和中不會超過 t，則將其包含在當前子集中，並遞迴調用dfs函數。 - 為了避免重複使用同一個數字，遞迴調用時，索引
it遞增。 - 程式碼使用一個
stk陣列來儲存當前正在考慮的子集，並在找到有效組合時，將其負數存入set中，因為題目要求輸出時數字由大到小排列。
複雜度分析
- 時間複雜度: O(2^n)，其中 n 是輸入數組的大小。在最壞的情況下，需要遍歷所有可能的子集。
- 空間複雜度: O(n + k)，其中 n 是輸入數組的大小，k 是找到的有效子集的數量。
stk陣列佔用 O(n) 空間，set佔用 O(k) 空間。
程式碼
#include <bits/stdc++.h>
using namespace std;
int t,n,ca,a[13],stk[13],x,y;
set <vector <int>> st;
set <vector <int>> :: iterator it;
void dfs(int it,int sum,int sz){
if(sum==t){
vector <int> a;
for(int i=0;i<sz;++i){
a.push_back(-stk[i]);
}
st.insert(a);
return;
}
for(int i=it+1;i<=n;++i){
if(sum+a[i]<=t){
stk[sz]=a[i];
dfs(i,sum+a[i],sz+1);
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
while(cin >> t >> n){
if(t==0&&n==0)break;
st.clear();
for(int i=1;i<=n;++i)
cin >> a[i];
cout << "Sums of " << t << ":\n";
dfs(0,0,0);
if(st.empty()){
cout << "NONE\n";
}
for(it=st.begin();it!=st.end();++it){
for(int i=0;i<(*it).size();++i){
if(i)cout << "+";
cout << -(*it)[i];
}
cout << "\n";
}
}
}