Advertisement
Kali_prasad

subsequence sum //O(T(2^n)),1 (qk21)

Apr 24th, 2022
28
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.95 KB | None | 0 0
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef pair<string,int> psi;
  10. typedef unordered_map<int,int> mii;
  11. typedef unordered_map<long long,long long> mll;
  12. typedef unordered_map<string,int> msi;
  13. typedef unordered_map<char,int> mci;
  14. typedef unordered_set<int> si;
  15. typedef unordered_set<long long> sll;
  16. typedef unordered_set<string> ss;
  17. typedef unordered_set<char> sc;
  18. typedef map<int,int> ormii;
  19. typedef map<long long,long long> ormll;
  20. typedef map<string,int> ormsi;
  21. typedef map<char,int> ormci;
  22. typedef set<int> orsi;
  23. typedef set<long long> orsll;
  24. typedef set<string> orss;
  25. typedef set<char> orsc;
  26. typedef vector<int> vi;
  27. typedef vector<string> vs;
  28. typedef vector<char> vc;
  29. typedef vector<ll> vll;
  30. typedef vector<vector<int>> vvi;
  31. typedef vector<vector<string>> vvs;
  32. typedef vector<vector<ll>> vvll;
  33.  
  34. #define FOR(i, a, b) for (auto i=a; i<=(b); i++)
  35. #define FORd(i,b,a) for (int i =b; i >= a; i--)
  36. #define sortinc(v) sort(v.begin(),v.end())
  37. #define sortdec(v) sort(v.rbegin(),v.rend())
  38. #define sz(x) (int)(x).size()
  39. #define mp make_pair
  40. #define pb push_back
  41. #define pob pop_back
  42. #define fi first
  43. #define se second
  44. #define ins insert
  45.  
  46. const int MOD = 1000000007;
  47. //type functions here
  48. int recurr(vi &v,int A,int B,int sum,int idx){
  49. if(idx==v.size())
  50. {
  51. if(A<=sum&&sum<=B) return 1;
  52. return 0;
  53. }
  54. int l=0,r=0;
  55. l=recurr(v,A,B,sum+v[idx],idx+1);
  56. r=recurr(v,A,B,sum,idx+1);
  57. return l+r;
  58.  
  59. }
  60.  
  61.  
  62. int main() {
  63. ios_base::sync_with_stdio(false);
  64. cin.tie(NULL);
  65.  
  66. int tc=1;
  67. cin>>tc;
  68. FOR(w,1,tc)
  69. {
  70. int n,A,B;
  71. cin>>n>>A>>B;
  72. vi v;
  73. FOR(i,1,n)
  74. {
  75. int temp;
  76. cin>>temp;
  77. v.pb(temp);
  78. }
  79. int count=recurr(v,A,B,0,0);
  80. cout<<count<<endl;
  81. }
  82. return 0;
  83. }
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement