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[] 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, 4, 6, 8], k = 8 
Output:   
[  
    [2, 2, 2, 2],  
    [2, 2, 4],  
    [2, 6],  
    [4, 4],  
    [8]  
]
Explanation: All the unique combinations whose sum is 8 is printed.
2+2+2+2 = 8
2+2+4 = 8
2+6 = 8
4+4 = 8
8 = 8

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