CODEWITHSUNDEEP
javascriptcombinations
emwhy
emwhy

Reputation: 113

I'm having some trouble visualizing the recursive calls of the Combination Sum problem?

The question is to find all of the unique combinations in a sorted array that sum to a given target value. For this example, let's say candidates=[2,3,6,7] and target=7. I watched some videos and I now understand the general algorithm of how to solve this problem. I also looked at a solution, but I'm having some trouble visualizing the recursive tree/each recursive call in the function. 

var combinationSum = function(candidates, target) {
    candidates.sort((a,b) => a-b)
    let result = []
    combSum(candidates, target, [], result, 0)
    return result 
};

function combSum(candidates, target, current, result, idx) {
    let n
    for (let i = idx; i < candidates.length; i++) {
        n = candidates[i]
        current.push(n)
        if (n === target) {
            result.push([...current])
        } else if (target > n) {
             combSum(candidates, target-n, [...current], result, i)
        }
        current.pop()
    }
 }

I know the first step is to try combinations starting with the first value in the array which is 2. So the function will try [2], then [2,2], then [2,2,2], and at this point the target is 1 which is less than n, so it skips both if statements and pops the last 2 off. Does the pop() method implicitly return to the previous function call on the call stack? It would return a value of 2 which never actually gets used, is this correct? There's no base case which is throwing me off.

Also, I know that since the array is sorted, we should know that if something like [2,2,3,3] doesn't work, then any other combination starting with the prefix of [2,2,3] also will not work. I don't see how the code addresses this though - how does it know to 'skip' these combinations? Like [2,2,3,6], etc.

EDIT: It's really late, I realized in my original post that I was looking at a different target value which was adding to my confusion... I fixed my post to reflect this. Sorry!!

Upvotes: 2

Views: 260

Answers (1)

collapsar
collapsar

Reputation: 17238

This answer does not address the visualization aspect but limits itself to your questions on specific details.

Preliminaries

The recursion is based on the idea that at any step in the incremental construction of a combination that sums to a target, the original problem needs to be solved for the difference of the original target and the sum of the current partial combination using the same set of candidates.

The parameters to combSum carry the following meaning:

  • candidates: The pool of numbers to pick from (ordered array)
  • target: The number to compose (integer)
  • current: The partial combination currently being completed (ordered array)
  • result: The combinations found so far
    (pseudo-lexicographically ordered array - prefixes come after their continuations)
  • idx: Minimum index of candidates element to be used in call.

Conceptually candidates and idx fold into a single actual parameter candidates.slice(i).

There are 2 invariants in the recursion:

  • The elements in the array current representing the partially constructed combination currently being completed are non-decreasing.
  • The sequence is built from left to right.
    In particular, no recursive call changes the elements of current that were present upon invocation.

The ordering of the candidates helps to avoid repeated constructions of the same sequence. Remember that in each recursive call the effective set of candidate elements is candidates.slice(i) with i non-decreasing and in every recursion level's loop, this level's i start value starts with the current value of i from the parent level.

Note that this only works if in candidates there are no duplicates of numbers that show up in a result combination, otherwise subsequences starting with this number will be computed multiple times producing several identical results ( Try combinationSum([1,4], 4) and combinationSum([1,1,4], 4); being precise, this will not occur if the multiplicity in candidates would equal the multiplicity in each result ... try combinationSum([2,2,5], 9) and combinationSum([2,5], 9))

1. Recursion base
The recursion base is the case n >= target ...

2. Skipping 'impossible' prefixes ... If n === target, the current partial combination is completed and added to the results. If n > target the current partial combination cannot be successfully completed (candidate numbers will only get bigger and the current one is already too large). However, the code does not cater for this condition ( it could with a if (n > target) break; statement at the end of the loop ).

3. Implicit return current.pop() restores the partial combination the current invocation of combSum started with. This is its purpose. While technically pop returns some value, but this value has already been used - it is the top element of current at the site of the recursive call!

Upvotes: 1

Related Questions