Given a list of distinct integers *nums* and a target integer *target*, find all
the possible combinations of *nums* which sums up to *target*. You may use a number
more than once.

**Examples**:

*Example 1*

**Input**: nums = [1, 2, 3], target = 4

**Output**: [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2]]

**Explanation**: Sum of all the four combinations is 4. Note how 1 is used mutiple
times in 1st and 2nd combination, and 2 is used multiple times in 4th combination.

*Example 2*

**Input**: nums = [2], target = 3

**Output**: []

## Approach: Backtracking

### Analysis

Since we have to find all possible combinations, we can use backtracking to solve the problem. There are 2 possible cases for all the elements in the array: either it can be added to combination or not.

In the *findSolution* function below, *idx* (current index)
and *currentSolution* is passed.

- If
*target*is 0, we have found a solution, thus push*currentSolution*to the*ans*2D vector. -
Otherwise -

- Loop from current index (not
*idx + 1*as an element can be used more than once) to end of the array - - If the current element is smaller than
*target*, add it to solution and recurse. - Once the function call (recursion) is completed, pop the current element and thus backtrack.

- Loop from current index (not

### Implementation

```
void findSolution(vector<int>& nums, vector<int>& currentSolution, vector<vector<int>> &ans, int idx, int target) {
if (target == 0) {
ans.push_back(currentSolution);
} else {
for (int i = idx; i < (int)nums.size(); i++) {
int cur = nums[i];
if (target >= cur) {
// consider the current number
currentSolution.push_back(cur);
findSolution(nums, currentSolution, ans, i, target - cur);
currentSolution.pop_back(); // backtrack
}
}
}
}
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
vector<int> currentSolution;
findSolution(nums, currentSolution, ans, 0, target);
return ans;
}
```

### Complexity Analysis

**Time Complexity**: Computation of the exact time complexity is difficult. However, we can give an upper bound of ${depth\;of\;recursion\;tree}^{no\;of\; maximum\;branchings} = O(N ^ {\lceil\frac{target}{min(nums)}\rceil})$, where $N$ is the number of elements in*nums*.**Space Complexity**: $O(N)$ extra for the recursion stack.