# 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;
}
```