All Articles

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.


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


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.


void findSolution(vector<int>& nums, vector<int>& currentSolution, vector<vector<int>> &ans, int idx, int target) {
    if (target == 0) {
    } else {
        for (int i = idx; i < (int)nums.size(); i++) {
            int cur = nums[i];
            if (target >= cur) {
                // consider the current number
                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  treeno  of  maximum  branchings=O(Ntargetmin(nums)){depth\;of\;recursion\;tree}^{no\;of\; maximum\;branchings} = O(N ^ {\lceil\frac{target}{min(nums)}\rceil}), where NN is the number of elements in nums.
  • Space Complexity: O(N)O(N) extra for the recursion stack.