SHARE
TWEET

Untitled

a guest Oct 12th, 2017 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <unordered_set>
  5. #include <sstream>
  6.  
  7. using namespace std;
  8.  
  9. // Return the total number of subsets of size exactly N in an array that sum up to a given number:
  10.  
  11. // Examples
  12. // arr = { 6, 5, 8, 1, 2, 10, 20, 3, 11}
  13. // target = 11;
  14. // N = 4
  15. // Ans - 1 { (1, 2, 3, 5) }
  16.  
  17. void saveResult(const vector<bool>& chosen, unordered_set<string>& result) {
  18.   stringstream str;
  19.   int pos = 0;
  20.   for(auto c : chosen) {
  21.     if(c) {
  22.       str << pos << '|';
  23.     }
  24.     ++pos;
  25.   }
  26.   result.insert(str.str());
  27.  
  28. void get_pairEx(vector<bool>& chosen, const vector<int>& arr, int target, unordered_set<string>& results) {
  29.   int l = 0;
  30.   int r = arr.size() - 1;
  31.   for(; l < r;) {
  32.     if(chosen[l]) {
  33.       ++l;
  34.     } else if(chosen[r]) {
  35.       --r;
  36.     } else {
  37.       int s = arr[l] + arr[r];
  38.       if(s < target) {
  39.         ++l;
  40.       } else if(s == target) {
  41.         chosen[l] = true;
  42.         chosen[r] = true;
  43.         saveResult(chosen, results);
  44.         chosen[false] = true;
  45.         chosen[false] = true;
  46.         ++l;
  47.         --r;
  48.       } else {
  49.         --r;
  50.       }
  51.     }
  52.   }
  53. }
  54.  
  55. void generate(vector<bool>& chosen,int startPos, int remain, const vector<int>& arr, int target, unordered_set<string>& results)
  56. {
  57.   if(remain > 0) {
  58.     for(int pos = startPos; pos < chosen.size(); ++pos) {
  59.       chosen[pos] = true;
  60.       generate(chosen, pos + 1, remain - 1, arr, target, results);
  61.       chosen[pos] = false;
  62.     }
  63.   } else {
  64.     int sum = 0;
  65.     for(int i = 0; i < chosen.size(); ++i) {
  66.       if(chosen[i]) {
  67.         sum += arr[i];
  68.       }
  69.     }
  70.     int actualTarget = target - sum;
  71.     if(actualTarget > 0) {
  72.       get_pairEx(chosen, arr, actualTarget, results);
  73.     }
  74.   }
  75. }
  76.  
  77. int get_subsets(vector<int> arr, int target, int N) {
  78.   sort(arr.begin(), arr.end());
  79.   vector<bool> chosen(arr.size(), false);
  80.   unordered_set<string> result;
  81.   generate(chosen, 0, N - 2, arr, target, result);
  82.   return result.size();
  83. }
  84.  
  85. // To execute C++, please define "int main()"
  86. int main() {
  87. //  cout << "ANS: " << get_pairs(vector<int>({6, 5, 8, 1, 2, 10, 20, 3, 11}), 11) << endl;
  88.   cout << "ANS: " << get_subsets(vector<int>({6, 5, 8, 1, 2, 10, 20, 3, 11}), 11, 4) << endl;
  89.   cout << "ANS: " << get_subsets(vector<int>({6, 5, 8, 1, 2, 10, 20, 3, 11, 4, 4}), 11, 4) << endl;
  90.   return 0;
  91. }
RAW Paste Data
Top