fork download 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. class Solution
  7. {
  8. public:
  9.   Solution(int startingCapacity = 100) { sol.reserve(startingCapacity); }
  10.   void Print()
  11.   {
  12.   	if (sol.empty())
  13.   	{
  14.   		cout << "== empty ==";
  15.   	}
  16.   	else
  17.   	{
  18.   		cout << sol[0];
  19.   	}
  20.   	for (size_t i = 1; i < sol.size(); i++)
  21.   	{
  22.   		cout << " " << sol[i];
  23.   	}
  24.   	cout << "\n";
  25.   }
  26.   bool HasValidSize()
  27.   {
  28.   	return sol.size() >= 2;
  29.   }
  30.   void Push(int number) { sol.push_back(number); }
  31.   void Pop() { sol.pop_back(); }
  32. private:
  33.   vector<int> sol;
  34. };
  35.  
  36. class Solver
  37. {
  38. public:
  39.   Solver(const vector<int>& v) : input(v), sol(v.size()) {}
  40.   int PrintSolutions(int sum)
  41.   {
  42.   	noSolutionsPrinted = 0;
  43.   	PrintSolutions(0, sum);
  44.   	return noSolutionsPrinted;
  45.   }
  46.  
  47. private:
  48.   const vector<int> input;
  49.   Solution sol;
  50.   int noSolutionsPrinted;
  51.  
  52.   void PrintSolutions(int startIndex, int sum)
  53.   {
  54.   	if (sum < 0 || startIndex == input.size()) return;
  55.   	if (sum == 0 && sol.HasValidSize())
  56.   	{
  57.   		sol.Print();
  58.   		noSolutionsPrinted++;
  59.   		return;
  60.   	}
  61.     for (size_t i = startIndex; i < input.size(); i++)
  62.     {
  63.     	sol.Push(input[i]);
  64.     	PrintSolutions(i + 1, sum - input[i]);
  65.     	sol.Pop();
  66.     }
  67.   }
  68. };
  69.  
  70. int main()
  71. {
  72. 	vector<int> v;
  73. 	int n, k;
  74. 	cin >> n >> k;
  75. 	v.reserve(n);
  76. 	while (n--)
  77. 	{
  78. 		int a;
  79. 		cin >> a;
  80. 		v.push_back(a);
  81. 	}
  82. 	Solver sol(v);
  83. 	cout << "Total number of solutions: " << sol.PrintSolutions(k) << "\n";
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin 
7 10
1 2 3 4 5 6 7
stdout 
1 2 3 4
1 3 6
1 4 5
2 3 5
4 6
Total number of solutions: 5
https://ideone.com/5owtwp
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!