a981 - 求和問題
題目描述
題目要求從給定的 N 個正整數中，找出所有加總等於 M 的組合。如果存在多個組合，則按照組合中數字由小到大的順序輸出。如果沒有任何組合可以加總到 M，則輸出 -1。
解題思路
本題採用深度優先搜尋 (DFS) 的回溯演算法來解決。首先，將輸入的 N 個正整數進行排序，以便於輸出時按照由小到大的順序排列。然後，使用 DFS 遍歷所有可能的組合。在 DFS 過程中，對於每個數字，都有兩種選擇：選擇該數字加入當前組合，或者不選擇該數字。如果選擇該數字，則從當前和中減去該數字，並繼續搜尋下一個數字。如果沒有選擇該數字，則直接搜尋下一個數字。當當前和等於 M 時，表示找到了一個有效的組合，則將該組合輸出。如果遍歷完所有數字後，仍然沒有找到任何有效的組合，則輸出 -1。
複雜度分析
- 時間複雜度: O(2^N)，因為在最壞情況下，需要遍歷所有可能的子集。
- 空間複雜度: O(N)，主要用於遞迴呼叫堆疊和儲存中間結果。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
int t,n[31],f[31];
bool check=0;
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
inline void dfs(int pos,int m){
if(!m){
check=1;
for(int i(0);i<t;++i)
if(f[i]){
write(n[i]);
putchar_unlocked(' ');
}
putchar_unlocked('\n');
return ;
}
if(pos>=t||n[pos]>m) return;
f[pos]=1;
dfs(pos+1,m-n[pos]);
f[pos]=0;
dfs(pos+1,m);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int m;
while(cin>>t>>m){
for(int i(0);i<t;i++) cin>>n[i];
sort(n,n+t);
memset(f,0,sizeof(f));
dfs(0,m);
if(!check){
putchar_unlocked('-');
putchar_unlocked('1');
putchar_unlocked('\n');
}
}
}