Combination Sum Leetcode Solution

The problem Combination Sum Leetcode Solution provides us an array or list of integers and a target. We are told to find the combinations that can be made using these integers any number of times that add up to the given target. So more formally, we can use the given integers any number of times such that they add to the given target. The required output is the combinations that have the sum equal to the given target.

Example

candidates = [2,3,6,7], target = 7

[[2,2,3],[7]]

Explanation: The given output sums up to the given target. Even if we try to come up with any other combination. We will end up arranging the same integers in a different order. But the order does not matter only the combinations do.

candidates = [2,3,5], target = 8

[[2,2,2,2],[2,3,3],[3,5]]

Explanation: Since we can use the same integer any number of times. In the output, we have used 2 multiple times in the first output. Similarly, in the second output 2 is repeated. We can verify that all the 3 outputs sum up to the given target.

Approach for Combination Sum Leetcode Solution

The approach for the problem is simple to find. Generally, in problems such as this, we are required to use backtracking. Because in such questions we are required to do a complete search and find the answer. So first, we sort the list of integers that is given to us. Afterward, we create a recursive function that keeps on adding an integer to the current temporary list of integers and keeping track of the remaining sum required to add up to the given target. So inside the recursive function, we keep two base cases. The first base case is to check if the remaining sum required goes negative. In that case, we will return from the recursive function. The second base case is our required condition if the remaining sum equals zero. If the remaining sum is zero this means that we have reached our required target. At that point, we push the current temporary list of integers into the output array of arrays.

Code

C++ code for Combination Sum Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

void backtrack(vector<vector<int>> &output, vector<int> &current, vector<int> &candidates, int remain, int start){
    if(remain < 0)
        return;
    else if(remain == 0)output.push_back(current);
    else {
        for(int i=start;i<candidates.size();i++){
            current.push_back(candidates[i]);
            backtrack(output, current, candidates, remain - candidates[i], i);
            current.pop_back();
        }
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> output;
    vector<int> current;
    sort(candidates.begin(), candidates.end());
    backtrack(output, current, candidates, target, 0);
    return output;
}

int main(){
  vector<int> cand = {2, 3, 6, 7};
  vector<vector<int>> output = combinationSum(cand, 7)	;
  for(auto x: output){
    for(auto y: x)
      cout<<y<<" ";
    cout<<endl;
  }
}

2 2 3 
7

Java code for Combination Sum Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<List<Integer>> combinationSum(int[] nums, int target) {
      List<List<Integer>> list = new ArrayList<>();
      Arrays.sort(nums);
      backtrack(list, new ArrayList<>(), nums, target, 0);
      return list;
  }
  
  private static void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
      if(remain < 0) return;
      else if(remain == 0) list.add(new ArrayList<>(tempList));
      else{ 
          for(int i = start; i < nums.length; i++){
              tempList.add(nums[i]);
              backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
              tempList.remove(tempList.size() - 1);
          }
      }
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int[] nums = {2, 3, 6, 7};
    List<List<Integer>> output = combinationSum(nums, 7);
    for(List<Integer> x: output){
      for(Integer y: x)
        System.out.print(y+" ");
      System.out.println();
    }
  }
}

2 2 3
7

Complexity Analysis

Time Complexity

O(N^(M/T + 1)) where N is the number of candidates, M is the smallest candidate among all the given integers, and T is the target value. Thus the time complexity is exponential and this is expected because the algorithm is recursive backtracking.

Space Complexity

O(T/M), where T is the target value and M is the minimal element among all other candidates.