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