Backpack 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;
}