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

Problem Note

  • All numbers (including target number k) will be positive integers.
  • The same number may be chosen from A[] 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: A[] = [2, 4, 6, 8], k = 8 
Output:   
[  
    [2, 2, 2, 2],  
    [2, 2, 4],  
    [2, 6],  
    [4, 4],  
    [8]  
]

Example 2

Input: A[] = [2,3,5], k = 8 
Output:  
[   
    [2,2,2,2],   
    [2,3,3],   
    [3,5] 
]