Understanding the differences between the DP solution and simple recursive. Which one is really better?

  • 6

    DP Solution:

    1. Start by creating an array of [target+1]. Call it arr.
    2. Initialize value at arr[candidates[i]] to be a set only containing {candidates[i]}.
    3. If there are any other indices j of arr that are non-empty, populate the arr[j+candidates[i]] with the set of arr[j] + candidates[i].

    Good for:
    If target is relatively small, and/or numbers in candidates are very dense.
    O(M*N) where M is target, and N is candidates.size()

    Recursive Solution:

    1. Start by recursing with an empty set on every element.
    2. DFS by adding the ith element on the temporary vector, calling the recursive function with the ith element added, then remove it.
    3. When the remaining is 0(we subtract target by candidate[i] every recursive call to candidate[i]), we add the result into the vector<vector<int>>.

    Good for:
    If M is overwhelmingly large.

    So I have an additional question: Though I see these 2 tradeoffs, in reality which one would dominate in terms of usefulness in the test cases given by whoever wrote them on leetcode?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.