knapsack problem

knapsack problem
Question:
give two integer n and m, select rand numbers from 1,2,3,...,n-1, n, 
let the sum of the combination is equal to  m.

print out all possible combinations.

Examples:
n = 8 m = 10
8 2
7 3
7 2 1
6 4
6 3 1
5 4 1
5 3 2
4 3 2 1

Answer:
#include <iostream>
#include <vector>

using namespace std;

void printNumbersWithSum(int n, int m, vector<int>& numbers) {
  if (m <= 0 || n <= 0)
    return;
  if (m == n) {
    for (int number : numbers)
      cout << number << " ";
    cout << n << endl;
  }
  numbers.push_back(n);
  printNumbersWithSum(n-1, m - n, numbers);
  numbers.pop_back();
  printNumbersWithSum(n-1, m, numbers);
}

int main() {
  vector<int> numbers;
  int n, m;
  cin >> n >> m;
  printNumbersWithSum(n, m, numbers);
  return 0;
}

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️