e179 - Runningman - 目標金額
題目描述
題目要求判斷在一組金額中，是否存在 k 個金額的組合，其總和恰好等於目標金額 t。
解題思路
此題可以使用深度優先搜尋 (DFS) 或回溯法來解決。我們從第一個金額開始，遞迴地選擇或不選擇每個金額。在遞迴過程中，我們追蹤已選擇的金額總和以及已選擇的金額數量。如果總和等於目標金額且選擇的金額數量等於 k，則找到解並返回 true。如果遞迴結束時仍未找到解，則返回 false。為了避免重複計算，遞迴調用時，起始索引需要遞增，確保每次只考慮尚未選擇的金額。
複雜度分析
- 時間複雜度: O(C(n, k))，其中 n 是金額的數量，k 是需要選擇的金額數量。在最壞情況下，我們需要檢查所有可能的 k 個金額組合。
- 空間複雜度: O(k)，主要來自於遞迴調用堆疊的深度。遞迴深度最多為 k。
程式碼
#include <iostream>
using namespace std;
long long int t,a[21];
int n,k;
bool ans;
inline void dfs(int it,long long int mon,int tk){
if(ans)return;
if(mon==t&&tk==k){
ans=1;
return;
}
for(int i=it+1;i<n;++i)
dfs(i,mon+a[i],tk+1);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> k >> t){
ans=0;
for(int i=0;i<n;++i)
cin >> a[i];
for(int i=0;i<n;++i)
dfs(i,a[i],1);
if(ans)
cout << "YES\n";
else
cout << "NO\n";
}
}