What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Combination Sum (With Code in C++ and Java)

  • May 04, 2022
  • 5 Minutes Read
Combination Sum (With Code in C++ and Java)

Getting started with competitive programming might seem difficult but once you start solving problems consistently it will help you to crack top companies interviews. One such important problem to practice is the Combination sum. This problem comes under the backtracking technique, one of the important topics to be covered to master competitive programming.

Problem statement

Given a list of integers and a target integer, we have to return a list of all unique combinations of candidates where the chosen numbers sum to the target. We can return the combinations in any order. The same number may be chosen from the list an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Sample Input:

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

Sample Output:

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

This problem statement can be solved in a number of ways using various approaches. We are going to solve this using the backtracking technique since we have to find all the possible combinations as the solution. So let's get an insight about backtracking before moving on to the approach to solving the problem.

What is Backtracking?

Backtracking is an algorithmic technique that traverses and finds every possible combination for a computational problem. If a solution is not suitable, that particular solution is eliminated and then we backtrack to try other possible combinations. Backtracking is implemented using recursion. The ultimate goal of using the backtracking approach is to use the brute force approach i.e., getting all possible solutions available for a problem under given conditions.

Algorithm

  1. First, sort the input list in ascending order to get the output in increasing order.
  2. Then, remove all the reoccurring values from the list, since duplicate values in the input list can produce duplicates in the output list. But we want output without any duplicates.
  3. We try to find the possible solutions with the recursive backtracking approach. We have two base conditions to check. One condition is to check whether the target value becomes negative at any point in time. If the target value becomes negative then it denotes that the particular solution is not suitable and we can ignore searching through it.
  4. And another one is checking whether the target value became zero. If the target value becomes zero then it denotes that we have attained the required target through searching. So we have to add that temporary list values to the output list.
  5. Else add the present index in that list to the current list and recursively call the function with target = target - cand[i] and index as the current i value, then remove that element.

Example

Consider the input list [2, 3, 5] for our example and the target sum is 8. We have to find all the possible combinations with this input. First sort all the elements in the list to make the further process easy.

Then for the first element 2, check whether the target value is negative or zero by subtracting the target value from 2. If both are not true then again call the function recursively until either of the condition is true. By repeating the recursive call we can reach a point where 2+2+2+2 equals 8. Thus we got one combination sum which is equal to the required target.

In a similar way, we get two more combinations 2+3+3 and 3+5 which also sums up the target. The process is more clearly explained with the following visual representation.

Example of combination sum

Java Code for Combination Sum

import java.util.*;

public class Main {
   public static List combinationSum(int[] candidates, int target) {
      List result = new ArrayList();
      Arrays.sort(candidates);
      backtrack(candidates, 0, target, new ArrayList(), result);
      return result;
   }
   public static void backtrack(int[] cand, int start, int target, List list, List result) {
      if (target < 0)
         return;
      if (target == 0)
         result.add(new ArrayList(list));
      for (int i = start; i < cand.length; i++) {
         list.add(cand[i]);
         backtrack(cand, i, target - cand[i], list, result);
         list.remove(list.size() - 1);
      }
   }
   public static void main (String args[]){
      int[] nums = {2, 3, 5};
      int target = 8;
      List output = combinationSum(nums, target);
      System.out.print(output);
   }
}

 

Output

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

 

C++ Code for Combination Sum

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

void findNumbers(vector<int>& ar, int sum,vector<vector<int> >& res, vector<int>& r,int i) {
	if (sum == 0) {
		res.push_back(r);
		return;
	}
	while (i < ar.size() && sum - ar[i] >= 0) {
		r.push_back(ar[i]); 
		findNumbers(ar, sum - ar[i], res, r, i);
		i++;
		r.pop_back();
	}
}

vector<vector<int> > combinationSum(vector<int>& ar, int sum) {
	sort(ar.begin(), ar.end());
	ar.erase(unique(ar.begin(), ar.end()), ar.end());
	vector<int> r;
	vector<vector<int> > res;
	findNumbers(ar, sum, res, r, 0);
	return res;
}
int main() {
	vector<int> ar;
	ar.push_back(2);
	ar.push_back(3);
	ar.push_back(5);
	int n = ar.size();

	int sum = 8; 
	vector<vector<int> > res = combinationSum(ar, sum);
	if (res.size() == 0) {
		cout << "Empty";
		return 0;
	}
	for (int i = 0; i < res.size(); i++) {
		if (res[i].size() > 0) {
			cout << " ( ";
			for (int j = 0; j < res[i].size(); j++)
				cout << res[i][j] << " ";
			cout << ")\n";
		}
	}
	return 0;
}

 

Output

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

 

Time complexity

The time complexity to solve the Combination sum using backtracking is (2^t )* k. Where k is the average length of the input and t is the length of the recursive call. This time is quite large but due to the recursive call, we can only able to implement it with this efficiency.

Space complexity

Considering the space complexity it will be k * n, where n is the number of combinations in the output and k is the average length of the input list. Hence if the combinations are more for the given input then space complexity will also increase.

Conclusion

As we have discussed an approach to solve the combination sum problem there are lot more problems you can explore to gain good knowledge about backtracking and competitive programming. If you are just getting started with competitive programming it will take some time to understand the concepts but being consistent and practicing more and more will definitely help to achieve good results. Our tutors are available 24/7 if you need help with data structures and algorithms.

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Keerthana Buvaneshwaran
I'm Keerthana Buvaneshwaran, a computer science engineering student who loves to write technical content as well. I'm always curious to explore and gain knowledge of new technologies. I'm grateful to share my knowledge through my writing which will help others to develop their skills.