Senior QA Engineer

This problem can be solved using recursion. 
Steps : 
1. Sort the array in increasing order.
2. Next, remove all the duplicates from array.
3. Now, use recursion and backtracking 
(A) If at any time sub-problem sum == 0 then insert that array to the result. 
(B) Else if sum < 0 then ignore and return.
(C) Else insert the present index in that array to the current vector and call the function with sum = sum-arr[index] and index = index, then pop that element from current index (backtrack) and call the function with sum = sum and index = index+1

Observations:
1. If all digits are sorted in descending order, then output is always “Not Possible”. 
2. If all digits are sorted in ascending order, then we need to swap last two digits. 
3. For other cases, we need to process the number from rightmost side to find the smallest of all greater numbers. 

Steps:
1. Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. If no such digit is found, then output is “Not Possible”.
2. Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. 
3. Swap the above found two digits.
4. Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the required output.