Combination Sum (With Solution)

Problem Statement

Given an array, a[], consisting of distinct elements, and a target sum, find all the unique combinations in the array where the sum is equal to the target sum. The same number from the array may be chosen any number of times.

Sample Test Cases :

Input 1:

a[] = [1, 2], sum = 4

Output 1:

Explanation 1:

All the possible combinations of elements that can sum up to sum are listed in the output.

Input 2:

a[] = [1, 3, 4, 5, 6], sum = 4

Output 2:

Explanation 2:

All the possible combinations of elements that can sum up to sum are listed in the output.

Approach

The approach to solving this problem is to use a naive backtracking-based recursive approach. The recursion will work based on the following choices when we are at the ith index:

• Take the ith element into the set under consideration.
• Do not take the ith element into the set under consideration.

Based on the states of the recursion, the algorithm is described as follows:

Base Cases:

• If the sum == 0, at any moment in the recursive calls, we add that list to the result list and return from the function.
• If the sum becomes negative or we reach the end of the array, we terminate that recursive call and return from that call.

Recursion:

• Insert the element at the current position into the list, and recurse for the value sum := sum – a[index]. Now pop this element from the list, and recurse for sum := sum. These recursive transitions correspond to the choices listed above.

Code / Implementation:

C++ Code Implementation

void getAllCombinationsUtil(vector < int > & a, int sum, int currIndex, vector < vector < int >> & result, vector < int > & curr) {
  if (sum == 0) {
    result.push_back(curr);
    return;
  } else if (sum < 0 || currIndex == (int) a.size()) {
    return;
  } else {
    curr.push_back(a[currIndex]);
    getAllCombinationsUtil(a, sum - a[currIndex], currIndex, result, curr);
    curr.pop_back();
    getAllCombinationsUtil(a, sum, currIndex + 1, result, curr);
  }
}
vector < vector < int >> getAllCombinations(vector < int > & a, int sum) {
  vector < vector < int >> result;
  vector < int > curr;
  int index = 0;
  getAllCombinationsUtil(a, sum, index, result, curr);
  return result;
}

Java Code Implementation

public static void getAllCombinationsUtil(int[] a, int sum, int currIndex, List < List < Integer >> result, List < Integer > curr) {
  if (sum == 0) {
    result.add(new ArrayList < > (curr));
    return;
  } else if (sum < 0 || currIndex == a.length) {
    return;
  } else {
    curr.add(a[currIndex]);
    getAllCombinationsUtil(a, sum - a[currIndex], currIndex, result, curr);
    curr.remove((int) curr.size() - 1);
    getAllCombinationsUtil(a, sum, currIndex + 1, result, curr);
  }
}
public static List < List < Integer >> getAllCombinations(int[] a, int sum) {
  List < List < Integer >> result = new ArrayList < List < Integer >> ();
  List < Integer > curr = new ArrayList < > ();
  int index = 0;
  getAllCombinationsUtil(a, sum, index, result, curr);
  return result;
}

Python Code Implementation

def getCombinationsUtil(a, sum, currIndex, result, curr):
    if sum == 0:
        result.append(list(curr))
        return
    elif sum < 0 or currIndex == len(a):
        return
    else:
        curr.append(a[currIndex])
        getCombinationsUtil(a, sum - a[currIndex], currIndex, result, curr)
        curr.pop()
        getCombinationsUtil(a, sum, currIndex + 1, result, curr)


def getCombinations(a, sum):
    result = []
    curr = []
    index = 0
    getCombinationsUtil(a, sum, index, result, curr)
    return result

Complexity Analysis:

• Time Complexity: Exponential
• Space Complexity: O(sum / minimum in array) // if recursion stack space is ignored

Practice Problem:

• Combination Sum

FAQs

Q.1: How could we have solved the problem if there were duplicates in the array?

Ans. We could remove the duplicates from the array and use the same recursive code to solve the problem.

Q.2: Why can’t we use Dynamic Programming to solve this problem?

Ans. In this problem, all the possible solutions are asked to be listed, rather than some optimal solution, so Dynamic Programming doesn’t help us in this problem.