# Find Combinations of a List Whose Sum is Equal to a Target

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.

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

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

### 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.