General question about 3sum/4sum questions


  • 0
    N

    for all the 3pointer/4pointer approach, I feel it's not easy to generalize that approach to address the general question like 'kSum'. Any suggestions?


  • 2
    D

    I guess there IS a general solution to k-sum problems, that is, recursion. This recursion function should know its target sum, current index, and remaining elements to use, and it solves the subproblem by choosing whether or not to pick the elements at current index.

    rec(target, index, remaining){
    return rec(target - array[index], index+1, remaining-1) "PLUS" rec(target, index+1, remaining);
    }

    if k is greater or equal than 2, I think sorting the array beforehand would be very helpful, since we are potentially doing a k-level loop anyway.

    Hope it helps:)


  • 0
    N

    would you mind giving out a more specific code example?


  • 0
    W

    according to this http://en.wikipedia.org/wiki/Subset_sum_problem
    Subset sum is generally an NP problem, then Xsum as a sub problem is also an NP in general scope. So even a general solution exists, it is not solvable for big size.
    Why Xsum is sub problem of Subset_sum ? -- If Xsum is non-NP, then Subset_sum may be divided as several Xsum sub-problem and is not NP either which is a contradiction.


  • 0
    Z

    I guess you can talking about dynamic programming method. But I am wondering for dp problem, you need define extra space to store the subset and subsum informaiton. How could you know all possible subsum? For instace, array[end_index][subsum]=t means the subset which ending with t has value subsum and in subarray from start to end_index. But how to know the range of subsum?Thanks in advanced.


  • 0
    W

    I have the same confusion . Can we solve the k sum problem using combination sum II method. Just change the result by only store k element subset.
    Is this count as a general way to solve K sum problem?


  • 0
    S

    Thanks for the info!


Log in to reply
 

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