Combination Sum II

First, sort the given array in non-decreasing order, it will help to generate combinations in non-decreasing order.  There will be 2 ^ N possible combinations of the given array, We create a vector ‘result’ and then we one by one check for all possible combinations, whether the sum of its elements is equal to ‘target’ or not. If the sum of the combination is equal to ‘target’, we will append it in vector ‘result’.

We finally sort vector ‘result’ in lexicographical order and remove all duplicates from it.

We can find all combinations of array both iteratively or recursively, Here, we will be using the iterative approach only.

Algorithm:

• Sort the given array ‘arr’.
• Create a vector ‘result’ It will keep all combinations having sum equal to ‘target’.
• Run a loop where ‘i’ ranges from 0 to 2^N-1, and in each iteration do the following -:
  • Create an empty vector ‘comb’
  • Run a loop where ‘j’ ranges from 0 to N - 1 and if ‘jth’ bit is set in ‘i’ then append element arr[j] in ‘comb’.
  • If the sum of all elements of ‘comb’ is equal to ‘target’ then add it in vector ‘result’
  • Sort the vector ‘result’
  • Remove all duplicates from vector ‘result’.  This can be done easily by either using built-in library functions or using the fact that duplicate entries are grouped together after sorting.
• Return ‘result’.

This problem can be solved using backtracking,  The idea is to incrementally build combinations to the solution set, and abandon a combination ("backtrack") as soon as it determines that the combination cannot achieve the target sum.  In order to avoid duplicates, we cannot consider each element separately. We need to consider a group of the unique integer while backtracking.

We first create an array ‘counters’ that will keep the frequency of each element in the array.

After that, we start from smallest to the largest unique integer in ‘arr’ and for each unique integer, we try to include each of its number of occurrence (from largest to smallest) in combination if it can lead to the target sum, otherwise backtrack to determine other such combinations.  Note, the order i.e smallest to largest unique integer and largest to smallest in occurrence will ensure that combination will generate in lexicographical order. 

Algorithm:

• This is a recursive approach.
• Iterate over the given array ‘arr’ and find the frequency of each unique element in that array, store these frequencies in array ‘counter’ such that ‘counter[i]’ gives the frequency of ith integer.
• We define a function ‘helper(comb, remain, curr, counter, result)’ where
  • ‘comb’: the combination we built so far at each step
  • ‘remain’: the remaining sum to reach the target sum.
  • ‘curr’: current unique element.
  • ‘counter’: Array having the frequency of each element.
  • ‘result’: the final combinations that have the target sum.
• At each invocation of the backtrack function, we do the following -:
  • If ‘remain’ is 0 then append the ‘comb’ in vector ‘result’ and return.
  • If ‘curr' is greater than max element present in the array ‘arr’ then return.
  • Run a while loop till ‘counter[curr]’ > 0 and ‘remain’ >= ‘curr’, in each iteration of this while loop append curr in array ‘comb’ and subtract curr from remain, after that decrement ‘counter[curr]’ by 1.
  • Run a loop till all the occurrence of ‘curr’ is not removed from ‘comb’. In each iteration of this loop call ‘helper(comb, remain, curr+1, counter, result)’ and then increment ‘remain’ by ‘curr’. This will search for all valid combination form by using different groups of ‘curr’
  • Call ‘helper(comb, remain, curr+1, counter, result)’ to search for all combinations that do not have integer ‘curr’.
• Return ‘result’.