sumSubsets

Given an array of integers arr and an integer num, find all possible unique subsets of arr that add up to num. Both the array of subsets and the subsets themselves should be sorted in lexicographical order.

Array A is lexicographically smaller than array B either if A is a prefix of B(and A ≠ B), or if there exists such index i (0 ≤ i < min(A.length, B.length)), that Ai < Bi, and for any j (0 ≤ j < i) Aj = Bj.

Example

• For arr = [1, 2, 3, 4, 5] and num = 5, the output should be
  sumSubsets(arr, num) = [[1, 4], [2, 3], [5]].

Input/Output

• [execution time limit] 0.5 seconds 

• [input] array.integer arr

  An array of integers.

  Guaranteed constraints:
  0 ≤ arr.length ≤ 20,
  1 ≤ arr[i] ≤ 1000.

• [input] integer num

  A non-negative integer.

  Guaranteed constraints:
  0 ≤ num ≤ 1000.

• [output] array.array.integer

  • A sorted array containing sorted subsets composed of elements from arr that have a sum of num. It is guaranteed that there are no more than 1000 subsets in the answer.