Is the standard judger wrong?


  • 0
    S

    Edit:

    My question is resolved, the judge is not wrong. Thanks to StefanPochmann.
    I'd like to leave my question here to remind that the input is a set without duplicates.


    The question requires:

    The solution set must not contain duplicate combinations.

    My solution passed all the leetcode testcases. However, when I test on my custom testcase

    [2,3,6,7,321,431,4,4,34,5,3,4,214,34,23,32]
    15
    

    My solution outputs:

    [[2,2,2,2,2,2,3],[2,2,2,3,3,3],[3,3,3,3,3],[2,2,2,2,3,4],[2,3,3,3,4],[2,2,3,4,4],[3,4,4,4],[2,2,2,2,2,5],[2,2,3,3,5],[2,2,2,4,5],[3,3,4,5],[2,4,4,5],[2,3,5,5],[5,5,5],[2,2,2,3,6],[3,3,3,6],[2,3,4,6],[2,2,5,6],[4,5,6],[3,6,6],[2,2,2,2,7],[2,3,3,7],[2,2,4,7],[4,4,7],[3,5,7],[2,6,7]]
    

    but the "expected answer" is:

    [[2,2,2,2,2,2,3],[2,2,2,2,2,2,3],[2,2,2,2,2,5],[2,2,2,2,3,4],[2,2,2,2,3,4],[2,2,2,2,3,4],[2,2,2,2,3,4],[2,2,2,2,3,4],[2,2,2,2,3,4],[2,2,2,2,7],[2,2,2,3,3,3],[2,2,2,3,3,3],[2,2,2,3,3,3],[2,2,2,3,6],[2,2,2,3,3,3],[2,2,2,3,6],[2,2,2,4,5],[2,2,2,4,5],[2,2,2,4,5],[2,2,3,3,5],[2,2,3,3,5],[2,2,3,4,4],[2,2,3,4,4],[2,2,3,4,4],[2,2,3,4,4],[2,2,3,4,4],[2,2,3,4,4],[2,2,3,3,5],[2,2,3,4,4],[2,2,3,4,4],[2,2,3,4,4],[2,2,3,4,4],[2,2,3,4,4],[2,2,3,4,4],[2,2,4,7],[2,2,4,7],[2,2,4,7],[2,2,5,6],[2,3,3,3,4],[2,3,3,3,4],[2,3,3,3,4],[2,3,3,3,4],[2,3,3,3,4],[2,3,3,3,4],[2,3,3,7],[2,3,3,3,4],[2,3,3,3,4],[2,3,3,3,4],[2,3,3,7],[2,3,4,6],[2,3,4,6],[2,3,4,6],[2,3,5,5],[2,3,3,3,4],[2,3,3,3,4],[2,3,3,3,4],[2,3,3,7],[2,3,4,6],[2,3,4,6],[2,3,4,6],[2,3,5,5],[2,4,4,5],[2,4,4,5],[2,4,4,5],[2,4,4,5],[2,4,4,5],[2,4,4,5],[2,6,7],[3,3,3,3,3],[3,3,3,3,3],[3,3,3,3,3],[3,3,3,6],[3,3,3,3,3],[3,3,3,6],[3,3,4,5],[3,3,4,5],[3,3,4,5],[3,3,3,3,3],[3,3,3,6],[3,3,4,5],[3,3,4,5],[3,3,4,5],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,5,7],[3,6,6],[3,3,3,3,3],[3,3,3,6],[3,3,4,5],[3,3,4,5],[3,3,4,5],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,5,7],[3,6,6],[4,4,7],[4,4,7],[4,4,7],[4,5,6],[4,4,7],[4,4,7],[4,5,6],[4,4,7],[4,5,6],[5,5,5]]
    

    where you can find many duplicates, such as [2,2,2,4,5]

    I wonder if the standard judger code is wrong.

    My Python code is as attached below. I used DP.
    dynam_table[x]==set[a1,a2,a3,...] means x can be reached by ai + sum of some candidates no greater than ai

    class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            candidates.sort()
            self.removeDuplicate(candidates,target)
            dynam_table = {0:set([0])}
            for i in xrange(len(candidates)):
                newtable = {}
                for part_sum in dynam_table:
                    part_sum = part_sum+candidates[i]
                    while part_sum<=target:
                        if part_sum in newtable:
                            newtable[part_sum].add(candidates[i])
                        else:
                            newtable[part_sum]=set([candidates[i]])
                        part_sum = part_sum+candidates[i]
                for newsum,newset in newtable.iteritems():
                    dynam_table[newsum] = dynam_table[newsum] | newtable[newsum] if newsum in dynam_table else newtable[newsum]
            result=[]
            self.traceback(result,dynam_table,target,[])
            return result
            
        def traceback(self,result,dynam_table,target,cur_path):
            if target==0:
                result.append(list(cur_path))
                return
            if target not in dynam_table:
                return
            cur_path.insert(0,-1)
            last = cur_path [1] if len(cur_path)>1 else float('inf')
            for x in dynam_table[target]:
                if x>last:
                    continue
                cur_path[0]=x
                self.traceback(result,dynam_table,target-x,cur_path)
            del cur_path[0]
               
        def removeDuplicate(self,candidates,target):
            i=0
            while i<len(candidates)-1:
                if candidates[i]==candidates[i+1] or candidates[i+1]>target:
                    del candidates[i+1]
                else:
                    i=i+1

  • 1

    The input is supposed to be a set, i.e., not contain duplicates. Your input contains duplicates.


  • 0
    S

    I see. Thank you for your answer, StefanPochmann.


Log in to reply
 

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