Combination Sum II

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
80 upvotes
Asked in companies
UberAdobe

Problem statement

You are given an array ‘arr’ of ‘n’ positive integers.


You are also given a positive integer ‘target’.


Your task is to find all unique combinations of elements of array ‘arr’ whose sum is equal to ‘target’. Each number in ‘arr’ may only be used once in the combination.


Elements in each combination must be in non-decreasing order and you need to print all unique combinations in lexicographical order.


Note: 
In lexicographical order, combination/array  ‘a’  comes before array ‘b’ if at the first index 'i' where 'a[i]' differs from 'b[i]', 'a[i]' < 'b[i]  or length of 'a' is less than 'b'.


Example: 
Input: ‘arr’ = [1, 2, 3, 1], ‘target’ = 5. 

Output: [[1,1,3], [2,3]]

Explanation:
All possible valid combinations with sum = 5 in lexicographical order are -:
(1, 1, 3)
(2, 3)


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
Then the first line of input contains two space-separated integers  ‘n’ and ‘target’ denoting the number of elements in ‘arr’ and the ‘target'.

The second line of input contains 'n' space-separated integers the elements of array ‘arr’.


Output Format: 
Print all possible valid combinations in a separate line in the lexicographical order. Elements in each combination must be in non-decreasing order.


Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1:
7 8
10 1 2 7 6 1 5


Sample Output 1:
1 1 6
1 2 5
1 7
2 6


Explanation For Sample Input 1:
Here ‘n’ = 7, 'arr' = [10, 1, 2, 7, 6, 1 , 5], and ‘target’ = 8
All unique combinations whose sum of elements is 8 are -:     

(1, 1, 6)  because, 1 + 1 + 6 = 8
(1, 2, 5)  because,  1 + 2 + 5 = 8
(1, 7)  because, 1 + 7 = 8                                                                                                               
(2, 6)  because,  2 + 6 = 8

Note that, elements in each combination are in non-decreasing order and all unique combinations are arranged in lexicographical order.


Sample Input 2:
5 5
1 2 3 1 5


Sample Output 2:
1 1 3
2 3
5


Expected Time Complexity:
Try to do this in O(2^n).


Constraints:
1 <= n <= 20
1 <= arr[i] <= 30
1 <= target <= 500

Time Limit: 1 sec
Hint

Find the sum of all 2 ^ N combinations.

Approaches (2)
Brute Force

First, sort the given array in non-decreasing order, it will help to generate combinations in non-decreasing order.  There will be 2 ^ N possible combinations of the given array, We create a vector ‘result’ and then we one by one check for all possible combinations, whether the sum of its elements is equal to ‘target’ or not. If the sum of the combination is equal to ‘target’, we will append it in vector ‘result’.

 

We finally sort vector ‘result’ in lexicographical order and remove all duplicates from it.

 

We can find all combinations of array both iteratively or recursively, Here, we will be using the iterative approach only.

 

Algorithm:

 

  • Sort the given array ‘arr’.
  • Create a vector ‘result’ It will keep all combinations having sum equal to ‘target’.
  • Run a loop where ‘i’ ranges from 0 to 2^N-1, and in each iteration do the following -:
    • Create an empty vector ‘comb’
    • Run a loop where ‘j’ ranges from 0 to N - 1 and if ‘jth’ bit is set in ‘i’ then append element arr[j] in ‘comb’.
    • If the sum of all elements of ‘comb’ is equal to ‘target’ then add it in vector ‘result’
    • Sort the vector ‘result’
    • Remove all duplicates from vector ‘result’.  This can be done easily by either using built-in library functions or using the fact that duplicate entries are grouped together after sorting.
  • Return ‘result’.
Time Complexity

O(N^2 * 2^N), where ‘N’ is the size of the array ‘Arr’.

 

Sorting the given array takes O(NlogN) times. 

It takes O(N*2 ^ N) time to find the sum of all 2 ^ N combinations.  

In the worst case, ‘result’ will have 2 ^ N combinations. Sorting it will take time O(N*2 ^ N*(log(2 ^ N))) i.e O(N^2 * 2^N)  (Note comparing two sequences takes O(N) time). 

Removing duplicates will take the time of order O(N * 2 ^ N). 

 

Thus, the final time complexity will be O(NlogN) + O(N*2 ^ N) + O(N ^ 2*2 ^ N) +O(N*2 ^ N) = O(N ^ 2*2 ^ N)

Space Complexity

O(N*2 ^ N), where ‘N’ is the size of the array ‘Arr’.

 

In the worst case, there will be 2 ^ N combinations in vector ‘result’, and the size of the combination can be up to ‘N’.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Combination Sum II
Full screen
Console