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.