Intuition:

For questions like printing combinations or subsequences, the first thing that should strike your mind is recursion.

How to think recursively?

Whenever the problem is related to picking up elements from an array to form a combination, start thinking about the “pick and non-pick” approach.

We use a recursive backtracking approach to find all combinations that sum up to the target.

We define a recursive function with the following parameters:
- Index — current position in the array.
- Target — remaining sum we need to achieve.
- DS (data structure) — to store the current combination.
At every step, we have two choices:
- Pick the element at the current index:
  - We reduce the target by arr[index].
  - Add arr[index] to the DS.
  - We stay on the same index since we can reuse the same element.
- Not pick the element:
  - We move to the next index.
  - Target remains unchanged.
  - Element is not added to the DS.
While backtracking, remove the last inserted element to explore new paths.
This process is repeated while index < array.size() for a given recursion call.
We can optionally stop recursion when target == 0, but here we allow the recursion to run fully for generalization.

Code