#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <sstream>

using namespace std;

// Return the total number of subsets of size exactly N in an array that sum up to a given number:

// Examples
// arr = { 6, 5, 8, 1, 2, 10, 20, 3, 11}
// target = 11;
// N = 4
// Ans - 1 { (1, 2, 3, 5) }

void saveResult(const vector<bool>& chosen, unordered_set<string>& result) {
  stringstream str;
  int pos = 0;
  for(auto c : chosen) {
    if(c) {
      str << pos << '|';
    }
    ++pos;
  }
  result.insert(str.str());
}

void get_pairEx(vector<bool>& chosen, const vector<int>& arr, int target, unordered_set<string>& results) {
  int l = 0;
  int r = arr.size() - 1;
  for(; l < r;) {
    if(chosen[l]) {
      ++l;
    } else if(chosen[r]) {
      --r;
    } else {
      int s = arr[l] + arr[r];
      if(s < target) {
        ++l;
      } else if(s == target) {
        chosen[l] = true;
        chosen[r] = true;
        saveResult(chosen, results);
        chosen[false] = true;
        chosen[false] = true;
        ++l;
        --r;
      } else {
        --r;
      }
    }
  }
}

void generate(vector<bool>& chosen,int startPos, int remain, const vector<int>& arr, int target, unordered_set<string>& results)
{
  if(remain > 0) {
    for(int pos = startPos; pos < chosen.size(); ++pos) {
      chosen[pos] = true;
      generate(chosen, pos + 1, remain - 1, arr, target, results);
      chosen[pos] = false;
    }
  } else {
    int sum = 0;
    for(int i = 0; i < chosen.size(); ++i) {
      if(chosen[i]) {
        sum += arr[i];
      }
    }
    int actualTarget = target - sum;
    if(actualTarget > 0) {
      get_pairEx(chosen, arr, actualTarget, results);
    }
  }
}

int get_subsets(vector<int> arr, int target, int N) {
  sort(arr.begin(), arr.end());
  vector<bool> chosen(arr.size(), false);
  unordered_set<string> result;
  generate(chosen, 0, N - 2, arr, target, result);
  return result.size();
}

// To execute C++, please define "int main()"
int main() {
//  cout << "ANS: " << get_pairs(vector<int>({6, 5, 8, 1, 2, 10, 20, 3, 11}), 11) << endl;
  cout << "ANS: " << get_subsets(vector<int>({6, 5, 8, 1, 2, 10, 20, 3, 11}), 11, 4) << endl;
  cout << "ANS: " << get_subsets(vector<int>({6, 5, 8, 1, 2, 10, 20, 3, 11, 4, 4}), 11, 4) << endl;
  return 0;
}