Combination Sum (With Solution)

Combination Sum

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

Confused about your next job?

In 4 simple steps you can find your personalised career roadmap in Software development for FREE



Expand in New Tab 

Output 1:

[1, 1, 1, 1] [1, 1, 2] [2, 2]

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:

[1, 1, 1, 1] [1, 3] [4]

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.
Recursion Tree

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:

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.

Previous Post
String Sort

Sort String (C++, Java, and Python)

Next Post
Longest Common Substring

Longest Common Substring

Total
0
Share