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 nondescending 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 nondescending 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 thetarget
, we then find a combination, so just add thestart
to theresult
and output the result. 
The value of the
start
is greater than thetarget
, then it is impossible to find the combination onwards because thecandidates
the list is sorted and all the following elements would be greater than thetarget
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
becomes0
then add thecandidate
array to the result as the values in thecandidate
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 fromstart
thanstart + 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.
Suggested Problem To Solve
 Letter combination of a phone number
 Find a unique combination of unique numbers that sum up to target
 Search word in a matrix
 Print all permutations of a string
Happy Coding!
Team AfterAcademy!!