Combination Sum

Difficulty: Medium

Asked in: Amazon, Facebook, Adobe

Understanding The Problem

Problem Description

Given an array of integers arr[] and a target number k , write a program to find all unique combinations in arr[] such that the sum of all integers in the combination is equal to k .

Problem Note:

All numbers (including target number k ) will be positive integers.
The same number may be chosen from arr[] the unlimited number of times.
Elements in a combination ( a1 , a2 , … , ak ) must be in non-descending order. (i.e, a1 ≤ a2 ≤ … ≤ ak ).
The combinations themselves must be sorted in ascending order, i.e., the combination with the smallest first element should be printed first.
The solution set must not contain duplicate combinations.

Example 1

Input: arr[] = [2, 3, 6, 7], k = 7 
Output:
[
  [7],
  [2,2,3]
]
Explanation: All the unique combinations whose sum is 7 is printed.
2+2+3 = 7
7 = 7

Example 2

Input: arr[] = [2,3,5], k = 8 
Output:  
[   
    [2,2,2,2],   
    [2,3,3],   
    [3,5] 
]
Explanation: All the unique combinations whose sum is 8 is printed.
2+2+2+2 = 8
2+3+3 = 8
3+5 = 8

Backtracking Solution

First of all, we need to sort the array, to ensure the combination to be unique and also the numbers in the combination to be listed in a non-descending order.

Then, we define a recursive function with the signature as:

backtrack(int[][] res, int[] candidate, int [] nums, int target, int start)

where "candidate" is the list that we could take numbers from, "result" is the list of combination that we have accumulated so far, "start" is the starting point at which we could take numbers from forwards (no backward), and "target" is the rest sum that we need to achieve. A recursion tree for the above example might look like this →

As a recursive function, the bottom cases for the backracking() are:

1. The value of the start is equal to the target , we then find a combination, so just add the start to the result and output the result.
The value of the start is greater than the target , then it is impossible to find the combination onwards because the candidates the list is sorted and all the following elements would be greater than the target as well.

Given the above recursive function, we could solve the problem by calling the function for each candidate starting from the start point.
For each candidate, we first try to add the candidate into the result , and then again starting from this candidate, we call the backtracking() function to obtain the result for the new target afterwards.

Solution Steps

Create a result array to store the valid sequences
Create a curr array that will store the current sequence found in the path of the recursion tree.
A backtrack function that will go into the recursion until the target is achieved, otherwise, it should backtrack to the previous phase as target becomes less than 0.
At any point in time, if target becomes 0 then add the candidate array to the result as the values in the candidate array must be sum up to the given target.
If those are not the cases then, one by one add the elements in the candidate array and recursively move forward.

Pseudo Code

int[][] combinationSum(int[] nums, int target) {
    int[][] result
    sort(nums)
    int[] curr
    backtrack(result, curr, nums, target, 0)
    return result
}

void backtrack(int[][] res, int[] candidate, int [] nums, int target, int start) {
    if(target < 0) 
        return
    else 
        if(target == 0) 
            res.add(candidate)
        else{
            for(int i = start; i < nums.length; i++) {
                candidate.add(nums[i])
                backtrack(list, candidate, nums, target - nums[i], i)
                // not i + 1 because we can reuse same elements
                candidate.remove(candidate.size() - 1)
            }
    }
}

Complexity Analysis

Time Complexity: O(l^k)

Where l is the length of the array, k is the length of the longest possible combination (namely target / minInArray ).
i.e. If the min value in the array is 1, and the target is 9, the longest length of possible combination is 9 (9/1).

Space Complexity: O(k), for storing the path, which could be k long at most.

Critical Ideas To Think

In the backtrack function why did we start the for loop from start than start + 1 ?
If the question requires that the same number can be chosen only one time, then what change should we have to make in the pseudo code?
What are the base cases of the recursion?
Why we are appending the sequence to our result only when the target is equal to zero?
Give a thought over the time complexity which is O(l^k).
Find problems where you can apply a similar approach.